题解 | #最大子矩阵#

描述： 已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。

输入描述： 输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。 再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。 已知矩阵中整数的范围都在[-127, 127]。

输出描述： 输出最大子矩阵的大小。

解答： 首先定义一个函数cslms来计算一维数组的连续子数组最大和，这也是这套题里的一道.

def cslms(ns: list):
    res, temp_max = ns[0], ns[0]
    for n in ns[1:]:
        temp_max = n + temp_max if temp_max > 0 else n
        res = temp_max if res < temp_max else res
    return res


n = int(input())
parsums = []
for i in range(n):
    lin = list(map(int, input().split()))
    # 部分和partial sum，即第i行前若干个数之和
    parsum = [lin[0]]
    for j in range(1,n):
        parsum.append(lin[j] + parsum[-1])
    parsums.append(parsum)

maxi = parsums[0][0]
for j in range(n):
    for i in range(j):
        # lin[k] 是输入矩阵第k行第i+2个数加到第j+1个数，i<j 
        lin = [parsums[k][j] - parsums[k][i] for k in range(n)]
        maxi = max(maxi, cslms(lin))
    # 补充 i=j 的情况
    lin = [parsums[k][j] for k in range(n)]
    maxi = max(maxi, cslms(lin))
print(maxi)