问题描述

输入一个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