Largest Submatrix Sum

Given a matrix that contains integers, find the submatrix with the largest sum.

Return the sum of the submatrix.

Assumptions

• The given matrix is not null and has size of M * N, where M >= 1 and N >= 1

Examples

{ {1, -2, -1, 4},

{1, -1, 1, 1},

{0, -1, -1, 1},

{0, 0, 1, 1} }

the largest submatrix sum is (-1) + 4 + 1 + 1 + (-1) + 1 + 1 + 1 = 7.

Approach: DP

Solution 0:

Check every Top, bottom, left, right O(N^4)

*

Count sum of each box we make O(N^2)

= O(N^6)

Solution 1: Memoize columns to prevent repeated index checks

Save sum of columns going down

ex: for column

orig sum

1 1

2 3

3 6

4 10

Check every top, bottom, left, right O(N^4)

*

Count of sum of summed column across O(N)

Solution 2: Memoize boxes to prevent repeated column checks

Save sum of boxes at its bottom-right position

Generate Memo array of bottom right summing. O(N^2)

+

Check top, bottom, left, right O(N^4)

*

Count sum of each box O(1)

= O(N^4)

Solution 3: Squish column sums into 1D array, Check for largest sum in 1D array

Largest sum of subarray O(N)

orig: 1 2 3 -7 4 5

Memo: 1 3 6 -1 4 9

Take summed columns, squish down

ex:

{ {1, -2, -1, 4},

{1, -1, 1, 1},

{0, -1, -1, 1},

{0, 0, 1, 1} }

Squished down into:

2 -4 0 7

For each ceiling , floor, we squish down O(N^2)

*

Add current layer to squished sum O(N)

+

Find largest sum in squished sums O(N)

= O(N^3)

public class Solution {
  public int largest(int[][] matrix) {
    int N = matrix.length;
    int M = matrix[0].length;
    int result = Integer.MIN_VALUE;
    for(int i = 0; i < N; i++){
      int[] curSquish = new int[M];
      for(int j = i; j < N; j++){
        addRow(matrix, curSquish, j);
        result = Math.max(result, largestSum(curSquish));
      }
    }
    return result;
  }

  private void addRow(int[][]matrix, int[]sum, int row){
    int[] curRow = matrix[row];
    for(int i = 0; i < sum.length; i++){
      sum[i] += curRow[i];
    }
  }

  private int largestSum(int[] input){
    int res = input[0];
    int tmp = input[0];
    for(int i = 1; i < input.length; i++){
      tmp= Math.max(tmp + input[i], input[i]);
      res = Math.max(res, tmp);
    }
    return res;
  }
}