Skip to content

Instantly share code, notes, and snippets.

@badbye
Created October 24, 2017 12:23
Show Gist options
  • Save badbye/78ca84a13a5f0f0676edd4f6ebd5bb8c to your computer and use it in GitHub Desktop.
Save badbye/78ca84a13a5f0f0676edd4f6ebd5bb8c to your computer and use it in GitHub Desktop.
# 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment