我正在尝试编写一个解决最大子数组问题的程序。我可以理解 Kadane 算法在 1-D 数组上的直觉以及在 2-D 数组上的 O(N^4) 实现背后的直觉。但是，我在理解二维数组上的 O(N^3) 实现时遇到了一些麻烦。
1）为什么我们将元素与同一列中前一行的元素相加？
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++)
array[i][j] += array[i-1][j];
}
2）我对算法的第二部分没有理解
试图在网上寻找解释，但无济于事。希望能在这里得到一些帮助！
提前致谢！
您知道如何使用 Kadane 算法计算一维数组上的最大和子数组。现在我们想为二维数组扩展这个算法。对于 O(N^3) 算法，我们有一个直觉。如果我们以某种方式创建 N^2 个子问题，然后尝试运行我们的 O(N) Kadane 算法，我们可以解决最大子数组问题。
所以基本上我们如何创建 N^2 子问题是通过迭代矩阵的所有顶部和底部行。然后我们尝试通过应用 kadane 的一维算法找到子数组存在的最佳列。因此，我们将这两行之间的数字逐列相加，然后在这个新形成的一维数组上应用 kadane 的一维算法。
但是我们这里有个问题。计算顶行和底行的所有 O(n^2) 范围的总和本身就是 O(n^4)。这个瓶颈可以通过修改我们的矩阵来克服，方法是将每个元素替换为该元素列中高于它的所有数字的总和。因此，现在我们可以通过减去矩阵中的适当数组来在 O(n) 时间内找出任意两行之间的数字之和。
java伪代码——
int kadane2D(int array[N][M]){
// Modify the array's elements to now hold the sum
// of all the numbers that are above that element in its column
for (int i = 1; i < N; i++) {
for (int j = 0; j < M; j++){
array[i][j] += array[i-1][j];
}
}
int ans = 0; // Holds the maximum sum matrix found till now
for(int bottom = 0; bottom < N; bottom++){
for(int top = bottom; top < N; top++){
// loop over all the N^2 sub problems
int[] sums = new int[N];
// store the sum of numbers between the two rows
// in the sums array
for(int i = 0; i < M; i++){
if (bottom > 0) {
sums[i] = array[top][i] - array[bottom-1][i];
} else {
sums[i] = array[top][i];
}
}
// O(n) time to run 1D kadane's on this sums array
ans = Math.max(ans, kadane1d(sums));
}
}
return ans;
}
对于了解Kadane 的一维算法的人来说，下面应该很容易理解。基本上，我们尝试使用prefix sumfor 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
我知道这是一个老问题。但谷歌没有正确的答案，或者他们工作过度。
不，这不是正确的方法。工作示例，在 O(N^2) 上：
/**
* Kadane 1d
* @return max sum
*/
public static int maxSum(int[] a) {
int result = a[0]; //get first value for correct comparison
int sum = a[0];
for (int i = 1; i < a.length; i++) {
sum = Math.max(sum + a[i], a[i]); //first step getting max sum, temporary value
result = Math.max(result, sum);
}
return result;
}
/**
* Kadane 2d
* @param array
* @return max sum
*/
public static int maxSum2D(int array[][]){
int result = Integer.MIN_VALUE; //result max sum
for (int i = 0; i < array.length; i++) {
int sum = maxSum(array[i]);
result = Math.max(result, sum);
}
return result;
}
完整示例：