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: Method O(n^4)

Step 1: preprocess to get each node's prefix sum from 0,0 to i,j including i,j

Step 2: for sum of (i,j) to (k,t) = m[k][t] - m[i - 1][ t] - m[k][j - 1] + m[i - 1][j - 1]

public class Solution {
  public int largest(int[][] matrix) {
    // Write your solution here.
//Step 1: preprocess to get each node's prefix sum from 0,0 to i,j including i,j
//Step 2: for sum of (i,j) to (k,t) = m[k][t] - m[i - 1][ t] - m[k][j - 1] + m[i - 1][j - 1]
    if (matrix == null || matrix.length == 0) {
      return 0;
    }
    int m = matrix.length;
    int n = matrix[0].length;
    int[][] prefixSum = new int[m][n];
    prefixSum[0][0] = matrix[0][0];
    //preprocess
    for (int i = 0; i < m; i++) {
      int rowPreSum = 0;
      for (int j = 0; j < n; j++) {
        rowPreSum += matrix[i][j];
        if (i == 0) {
          prefixSum[i][j] = rowPreSum;
        } else {
          prefixSum[i][j] = prefixSum[i - 1][j] + rowPreSum;
        }
      }
    }

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {

      }
    }

    //not finished here, step two. 
    return 0;

  }
}

O(n^3) compress two rows, and do prefix sum .

Approach: Step 1: preprocess to calculate each column's prefix sum.

step 2: use the stored prefix column sum, calculate the 1D sum array from two points.

then. do the largest sum of sub array.

public class Solution {
  public int largest(int[][] matrix) {
    // Write your solution here.
    if (matrix == null || matrix.length == 0) {
      return 0;
    }
    int m = matrix.length;
    int n = matrix[0].length;
    int result = Integer.MIN_VALUE;
    int[] array = new int[n];
    int[][] colSum = new int[m][n];
    //preprocess
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (i == 0) {
          colSum[i][j] = matrix[0][j];
        } else {
          colSum[i][j] = colSum[i - 1][j] + matrix[i][j];
        }
      }
    }

    for (int upperRow = 0; upperRow < m; upperRow++) {
      for(int lowerRow = upperRow; lowerRow < m; lowerRow++) {
        for (int i = 0; i < n; i++) {
          array[i] = colSum[lowerRow][i] - colSum[upperRow][i] + matrix[upperRow][i];
        }
        int temp = largestSub(array);
        result = Math.max(temp, result);
      }
    }
    return result;
  }

  private int largestSub(int[] array) {
    if (array == null || array.length == 0) {
      return 0;
    }
    int cur = array[0];
    int result = cur;

    for (int i = 1; i < array.length; i++) {
      cur = Math.max(array[i], cur + array[i]);
      result = Math.max(result, cur);
    }
    return result;
  }
}