题解 | #最大子矩阵#

# 求解一维最大子数组的子函数，我们将问题转化为多个一维子问题
def maxSubArray(nums):
    tmp = [nums[0]]
    for i in range(1, len(nums)):
        if tmp[i-1] < 0:
            tmp.append(nums[i])
        else:
            tmp.append(tmp[i-1] + nums[i])
    return max(tmp)

# 读入数据
n = int(input())
matrix = []
for _ in range(n):
    row = list(map(int, input().split()))
    matrix.append(row)

# 每一列求前缀和
preSum = [[0] * n]
preSum.append(matrix[0])
for i in range(1, n):
    row = [0] * n 
    for j in range(n):
        row[j] = preSum[-1][j] + matrix[i][j] 
    preSum.append(row)
    
# 遍历每种行i行j的组合, 利用前缀和求出i, j 之间每一列的和
# 此时问题转化为一维最大子数组的和问题
maxSubMatrix = -float('inf')
for i in range(n):
    for j in range(i, n):
        nums = [0] * n 
        for k in range(n):
            nums[k] = preSum[j+1][k] - preSum[i][k]
        res = maxSubArray(nums)
        maxSubMatrix = max(res, maxSubMatrix)
print(maxSubMatrix)