题解 | #最大子矩阵#
最大子矩阵
https://www.nowcoder.com/practice/a5a0b05f0505406ca837a3a76a5419b3
N = input().strip()
N = int(N)
matrix = list()
for i in range(N):
M = input().strip()
Mn = M.split(' ')
matrix.append([int(_) for _ in Mn if _])
if N == 1:
print(matrix[0][0])
else:
cp = [[0] * N]
cp += matrix
for i in range(1, N + 1):
for j in range(N):
cp[i][j] = cp[i-1][j] + matrix[i - 1][j]
value = [-1e20] * (N + 1)
max_value = list()
for i in range(1, N + 1):
for j in range(i, N + 1):
for a in range(N):
tmp = cp[j][a] - cp[i - 1][a]
value[a] = max(value[a - 1] + tmp, tmp)
max_value.append(max(value))
print(max(max_value))
