2.5 Largest submatrix sum

Assumption: given matrix is not null and size n*m, n & m >= 1

Input: int[][] matrix

Output: int largest sum of submatrix

Solution:

n*m * n*m possible submatrices

Store prefixSum for matrix, locate bottom-right corner of each area

Given points in the matrix: (k,t) as top-left of the square, (i, j) as bottom-right

sum[(k,t)(i,j)] = prefixSum[i][j] - prefixSum[k-1][j] - prefixSum[i][t-1] + prefixSum[k-1][t-1]

e.g.				        prefixSum
1   2  3  4  5			1  3  6  10  15
-1  1  2  1  2			0  3  8  13   20
3   1  2  1  3			3  7  14 20  30

→ prefixSum[i][j] = prefixSum[i - 1][j] + prefixSumSameRow[i][j]

1. dp[i][j] represents prefixSum[(0,0), (i, j)] in the matrix

2. Base case: prefixSumSameRow[i][0] = matrix[i][0]

3. Induction rule: prefixSumSameRow[i][j] = [i][j-1] + matrix[i][j]

4. Pre-process the prefixSum for each column, then for each row

TC: n*n prefixSum for each col * m for each row = O(n * n * m)

SC: O(m)

public int largest(int[][] matrix) {
  int n = matrix.length;
  int m = matrix[0].length;
  int res = Integer.MIN_VALUE;

  for (int i = 0; i < n; i++) {
    int[] array = new int[m];
    for (int j = i; j < n; j++) {
      colSum(array, matrix[j]);		//Pre-process prefixSum for each column
      res = Math.max(res, prefixSum(array));		//prefixSum for each row
    }
  }
  return res;
}

private void colSum(int[] array, int[] row) {
  for (int i = 0; i < array.length; i++) {
    array[i] += row[i];
  }
}

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