問題描述
輸入一個N*N的矩陣（有正有負(fù)）簿盅，輸出最大的子矩陣和
輸入
3
1 2 -3 3 4 -5 -5 -6 -7
輸出
10
思路
- 處理輸入歉甚，變成N*N的矩陣
- 中心思想
先理解一維數(shù)組的最大子段和扛点，上下行加在一起就是一個數(shù)組了相味，一樣的思想
上下行相加芭届，得到的是第一行和每兩行相加的矩陣
下一步就是找出所有的行組合颇玷，再計算每一行的最大子段和,
第i行到第j行的所有相加結(jié)果函數(shù)（row_sum(arr)）淳衙，求組合的最大子段函數(shù)（list_max）
- 最后在結(jié)果集合里找到最大值并輸出
- 注：本方法針對NN矩陣蘑秽，NM的矩陣在輸出和循環(huán)的時候改一下就好（eg：row = len(arr）,col = len(arr[0])),本方法沒有返回具體的子矩陣
python
def main():
# 獲得二維數(shù)組
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)
#存放所有行級子矩陣最大結(jié)果
res_max = []
# 重要思想：先理解一維數(shù)組的最大子段和，上下行加在一起就是一個數(shù)組了箫攀，一樣的思想
# 上下行相加肠牲，得到的是第一行和每兩行相加的矩陣
# 下一步就是找出所有的行組合，再計算每一行的最大子段和,
# 第i行到第j行的所有相加結(jié)果
# 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):
# 當(dāng)前值加上后有沒有不加大
temp = max(temp + arr_number[i], arr_number[i])
# 判斷當(dāng)前情況后靴跛，再比較和之前的哪個大
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
