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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://llssff.gitbook.io/coding-problems/dynamic-programming/largest-submatrix-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.