对于了解Kadane 的一维算法的人来说,下面应该很容易理解。基本上,我们尝试使用prefix sum
for each rows 将 2D 矩阵转换为 1D。对于每个前缀和行,我们只应用 Kadane 的一维算法。
只需发布工作 Python 代码:
class Kadane2D:
def maxSumRetangle(self, grid):
def kadane1D(arr):
curmax, maxsofar = 0, float('-inf')
for a in arr:
curmax = max(a, curmax + a)
maxsofar = max(curmax, maxsofar)
return maxsofar
m, n, ans = len(grid), len(grid[0]), float('-inf')
colCum = [[0] * n]
for row in grid:
colCum.append([pre + now for pre, now in zip(colCum[-1], row)])
for top in range(1, m + 1):
for bottom in range(top, m + 1):
sums = [b - t for b, t in zip(colCum[bottom], colCum[top - 1])]
ans = max(ans, kadane1D(sums))
return ans
grid = [[1, 2, - 3], [3, 4, -6]]
assert Kadane2D().maxSumRetangle(grid) == 10
grid = [[1, 2, -1, -4, -20],
[-8, -3, 4, 2, 1],
[3, 8, 10, 1, 3],
[-4, -1, 1, 7, -6]]
assert Kadane2D().maxSumRetangle(grid) == 29