java - 理解 Kadane 的二维数组算法

Question

我正在尝试编写一个程序来解决 maximum subarray problem .我可以理解 Kadane 算法在一维数组上的直觉以及 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)我对算法的第二部分没有理解

尝试在网上寻找解释，但无济于事。希望在这里得到一些帮助!

提前致谢!

Answer 1

您知道如何使用 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;
    }