Understanding Kadane's Algorithm for 2-D Array

Question

I'm trying to write a program which solves the maximum subarray problem. I can understand the intuition behind Kadane's Algorithm on a 1-D array as well as the O(N^4) implementation on a 2-D array. However, I am having some trouble understanding the O(N^3) implementation on a 2-D array.

1) Why do we add up the elements with those from the previous rows within the same column?

for (int i = 1; i <= N; i++) {
  for (int j = 1; j <= M; j++) 
       array[i][j] += array[i-1][j];
}

2) I have no understanding of the second part of the algorithm

Tried looking for an explanation on the web but to no avail. Hope to get some help here!

Thanks in advance!

Answer 1

You know how to compute maximum sum sub-array on a 1D array using Kadane's algorithm. Now we want to extend this algorithm for the 2D array. For an O(N^3) algorithm, we have an intuition. If we somehow create N^2 sub problems and then try to run our O(N) Kadane's algorithm, we can solve the maximum sub array problem.

So basically how we create the N^2 sub problems is by iterating over all the top and bottom rows of the matrix. Then we try to find the optimal columns between which the sub array exists by applying kadane's 1D algorithm. We thus sum the numbers between these two rows column wise and then apply kadane's 1D algorithm on this newly formed 1D array.

But we have a problem here. Computing the sums for all the O(n^2) ranges of the top and bottom rows will itself be O(n^4). This bottle neck can be overcome by modifying our matrix by replacing each element with the sum of all the numbers that are above it in that element's column. Thus, now we can find out the sum of numbers between any two rows in O(n) time by subtracting the appropriate arrays in the matrix.

The java pseudo code -

    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;
    }

Answer 2

For people who understand the Kadane's 1D algorithm, below should be easy to understand. Basically we try to convert the 2D matrix into 1D by using the prefix sum for each rows. And for each prefix sum row, we just apply the Kadane's 1D algorithm.

Just posting the working Python code:

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

Answer 3

I know it's an old question. But Google doesn't have the right answers, or they're overworked.

No, this is no correct way. Working example, on 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;
  }

Fully examples:

• Easy: https://pastebin.com/Qu1x0TL8
• Supplemented: https://pastebin.com/Tjv602Ad
• With indexes: https://pastebin.com/QsgPBfY6