max_series_in_matrix.py

# encoding: utf8

"""
Created on 2017.10.24

@author: yalei
"""

import numpy as np


def maxSum(list_of_nums):
    maxsum = 0
    maxtmp = 0
    start = 0
    length = 0
    start_res = 0
    length_res = 0
    for i in range(len(list_of_nums)):
        if maxtmp <= 0:
            maxtmp = list_of_nums[i]
            start = i
            length = 1
        else:
            maxtmp += list_of_nums[i]
            length += 1
        if (maxtmp > maxsum):
            maxsum = maxtmp
            length_res = length
            start_res = start
    return start_res, length_res, maxsum


def sum_mat(x, debug=False):
    # 横
    # 竖
    # 斜
    m, _ = x.shape
    max_res = 0
    direction = None
    length_res = 0
    start_x = 0
    start_y = 0
    for i in range(0, m):
        # print '-' * 10
        # print 'i-----------: ', i
        ##############################################
        start, length, max_h = maxSum(x[i, :])
        if max_h > max_res:
            direction = '右'
            start_x = i
            start_y = start
            length_res = length
            max_res = max_h

        ##############################################
        start, length, max_s = maxSum(x[:, i])
        if max_s > max_res:
            direction = '下'
            length_res = length
            max_res = max_s
            start_x = start
            start_y = i

        ##############################################
        # 右下
        child_seq = zip(range(0, m - i), range(i, m))
        start, length, max_youxia = maxSum([x[k, t] for k, t in child_seq])
        if max_youxia > max_res:
            direction = '45度 右下'
            length_res = length
            max_res = max_youxia
            start_x, start_y = child_seq[start]

        ##############################################
        child_seq = zip(range(i, -1, -1), range(0, i + 1))

        start, length, max_youshang = maxSum([x[k, t] for k, t in child_seq])
        if max_youshang > max_res:
            direction = '45度 右上'
            length_res = length
            max_res = max_youshang
            start_x, start_y = child_seq[start]

        ##############################################
        child_seq = zip(range(m - 1 - i, m), range(m - 1, m - 2 - i, -1))
        start, length, max_youxia_sub = maxSum([x[k, t] for k, t in child_seq])
        if max_youxia_sub > max_res:
            direction = '45度 左下'
            length_res = length
            max_res = max_youxia_sub
            start_x, start_y = child_seq[start]

        ##############################################
        child_seq = zip(range(i, m), range(0, m - i))
        start, length, max_youshang_sub = maxSum([x[k, t] for k, t in child_seq])
        if max_youshang_sub > max_res:
            direction = '45度 右下'
            length_res = length
            max_res = max_youshang_sub
            start_x, start_y = child_seq[start]
    return direction, start_x, start_y, length_res, max_res


if __name__ == '__main__':
    # mat = np.array([[-3, 6, 4, 1], [8, -7, 5, 2], [3, 1, 7, 4], [-2, 8, -5, 9]])
    # x2 = [[-3, 6, 4, 1, 0], [8, -7, 5, 2, 0], [3, 1, 7, 4, 0], [-2, 8, -5, 9, 0], [1, 2 ,3, 4, 5]]
    # x2 = [[1, 2,10],[3, 4,2],[7, 6, 8]]
    # mat = np.array(x2)
    # print mat
    import time

    mat = np.loadtxt('matrix.txt')
    t1 = time.time()
    direction, start_x, start_y, length_res, max_res = sum_mat(mat, False)
    print 'time cost: ', time.time() - t1
    print 'direction:%s, start_x:%s, start_y:%s, length:%s, max_sum:%s ' % (
    direction, start_x, start_y, length_res, max_res)