题解 | O(n^3)解法 #最大子矩阵#

n=int(input())
mat=[]
for _ in range(n):
    mat.append([int(i) for i in input().split()])
m,n=len(mat),len(mat[0])
pre=[[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+mat[i-1][j-1]
def find(r1,c1,r2,c2):
    return pre[r2+1][c2+1]-pre[r2+1][c1]-pre[r1][c2+1]+pre[r1][c1]
res=float("-inf")
for r1 in range(n):
    for r2 in range(r1,n):
        total=0
        for c in range(n):
            total=max(total+find(r1,c,r2,c),find(r1,c,r2,c))
            res=max(res,total)
print(res)