问题描述
输入一个N*N的矩阵（有正有负），输出最大的子矩阵和
输入
3
1 2 -3 3 4 -5 -5 -6 -7
输出
10
思路
- 处理输入，变成N*N的矩阵
- 中心思想
先理解一维数组的最大子段和，上下行加在一起就是一个数组了，一样的思想
上下行相加，得到的是第一行和每两行相加的矩阵
下一步就是找出所有的行组合，再计算每一行的最大子段和,
第i行到第j行的所有相加结果函数（row_sum(arr)），求组合的最大子段函数（list_max）
- 最后在结果集合里找到最大值并输出
- 注：本方法针对NN矩阵，NM的矩阵在输出和循环的时候改一下就好（eg：row = len(arr）,col = len(arr[0])),本方法没有返回具体的子矩阵
python
def main():
# 获得二维数组
n = int(input())
arr = input()
arr_group = arr.split(" ")
arr_number = []
for i in range(n):
arr_row = []
for item in arr_group[i * n:i * n + n]:
arr_row.append(int(item))
arr_number.append(arr_row)
#存放所有行级子矩阵最大结果
res_max = []
# 重要思想：先理解一维数组的最大子段和，上下行加在一起就是一个数组了，一样的思想
# 上下行相加，得到的是第一行和每两行相加的矩阵
# 下一步就是找出所有的行组合，再计算每一行的最大子段和,
# 第i行到第j行的所有相加结果
# print(row_sum(arr_number))
for i in range(n):
for j in range(i,n):
res_row = row_sum(arr_number[i:j+1])
res_max.append(list_max(res_row))
print(max(res_max))
def list_max(arr_number):
temp = arr_number[0]
res = temp
n = len(arr_number)
if n < 1:
print(0)
else:
for i in range(1, n):
# 当前值加上后有没有不加大
temp = max(temp + arr_number[i], arr_number[i])
# 判断当前情况后，再比较和之前的哪个大
res = max(temp, res)
return res
#计算第i行到第j行的和
def row_sum(arr):
if len(arr) == 1:
return arr[0]
res = []
for i in range(len(arr[0])):
sum = 0
for j in range(len(arr)):
sum+=arr[j][i]
res.append(sum)
return res
if __name__ == '__main__':
main()
# 1 2 -3 3 4 -5 -5 -6 -7
