4

我正在尝试编写一个解决最大子数组问题的程序。我可以理解 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)我对算法的第二部分没有理解

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

提前致谢!

4

3 回答 3

13

您知道如何使用 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;
    }
于 2014-02-21T16:50:27.193 回答
2

对于了解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
于 2019-10-15T02:25:07.213 回答
0

我知道这是一个老问题。但谷歌没有正确的答案,或者他们工作过度。

不,这不是正确的方法。工作示例,在 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;
  }

完整示例:

于 2018-03-30T13:15:46.467 回答