# 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)

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