Question

link

Given a 2D array, find the maximum sum subarray in it. For example, in the following 2D array, the maximum sum subarray is highlighted with blue rectangle and sum of this subarray is 29.

Analysis

Note that this is a difficult(and high-frequency) question.

Try convert this question to “max sum in 1D array” by sum up all numbers in the same column. (we know that in 1D array, the algo runs O(n) time)

There’s in total O(n²) combinations of ways to sum up a column. So the total time complexity is O(n³).

Solution

1. Traverse matrix at row level.

2. have a temporary 1-D array and initialize all members as 0.

3. For each row do following

   1. add value in temporary array for all rows below current row
   2. apply 1-D kadane on temporary array
   3. if your current result is greater than current maximum sum, update.

Code

written by me

public int maxSum(int[][] A) {
    int m = A.length;
    int n = A[0].length;
    int maxResult = Integer.MIN_VALUE;
    for (int i = 0; i < m; i++) {
        int[] temp = new int[n];
        for (int j = i; j < m; j++) {
            // from row#i to row#(m-1), add the number into temp[]
            for (int k = 0; k < n; k++) {
                temp[k] += A[j][k];
            }
            // find max sum for 1D array
            maxResult = Math.max(maxResult, maxSum(temp));
        }
    }
    return maxResult;
}

private int maxSum(int[] B) {
    int sumSoFar = 0;
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i < B.length; i++) {
        maxSum = Math.max(maxSum, sumSoFar + B[i]);
        sumSoFar = Math.max(0, sumSoFar + B[i]);
    }
    return maxSum;
}