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