题解 | #最大子矩阵# Python3 + 简单解释

import sys

# 对于一个最大和的子矩阵来说，多加上下左右任意一行或着一列，该行和列的和都为0
# 固定矩阵的最上行和最下行，相当于遍历每一列使得连续几列的最大
# 假设该列是 dp[i], dp[i] = max(sum(i列),dp[i-1]+ sum(i列))
# sum[i]列这个可以通过求前缀和获得
n = int(input())

col_sum = [[0]*n for _ in range(n)]

arr = []
for i in range(n):
    data = input().strip().split(' ')
    data = [v for v in data if len(v)>0]
    nums = list(map(int,data))
    arr.append(nums)
    for j,num in enumerate(nums):
        if i == 0:
            col_sum[i][j] = num
        else:
            col_sum[i][j] = col_sum[i-1][j] + num

max_sum = -128

for x1 in range(n):
    for x2 in range(x1,n):
        dp = [0]* n
        for y in range(n):
            if x1 == 0:
                cur_col_sum = col_sum[x2][y]
            else:
                cur_col_sum = col_sum[x2][y] - col_sum[x1-1][y]
            if y == 0:
                dp[y] = cur_col_sum
            else:
                dp[y] = max(dp[y-1]+cur_col_sum, cur_col_sum)
            max_sum = max(max_sum, dp[y])

print(max_sum)