两次前缀和
- 对每一行分别求前缀和
- 穷举左右边界, 对于每一组左右边界之间的任意一行的区间和, 可以在O(1)时间内求出来.
- 穷举下边界, 得到一个一维的前缀和
- 基于这个一维的前缀和, 只要找到其中一个区间, 它的区间和最大, 就等于最大子矩阵的和.
- 这个区间求解方法很简单: max(前缀和 - 前缀和一阶滞后项的累加最小值), 经典套路了, 模板问题是: 已知一段价格走势, 求股票买卖一次最大能够赚多少钱?
时间复杂度
穷举左右边界, 穷举下边界, 三重循环, 因此, 时间复杂度是O(N^3)
Python 代码
N = int(input())
data = []
while len(data) < N * N:
data.extend(list(map(int, input().split())))
A = []
for i in range(N):
row = data[i * N : (i + 1) * N]
for j in range(1, N):
row[j] += row[j - 1]
A.append([0] + row)
#print(A)
M = float("-inf")
for j1 in range(N + 1):
for j2 in range(j1 + 1, N + 1):
MIN = 0
S = 0
for i in range(N):
e = A[i][j2] - A[i][j1]
S += e
M = max(M, S - MIN)
MIN = min(MIN, S)
print(M)