## Max submatrix sum in a matrix

Given an NxN matrix of positive and negative integers, write code to find the sub- matrix with the largest possible sum.

Thoughts:
Go through each submatrix ($O(n^4)$ of them) and compute their sums, keeping track of the curren maximum. Without additional optimization, the computation of sums cost $O(n^4)$, giving total a $O(n^6)$ algorithm. We can precompute some sums to reduce the total costs to $O(n^4)$:
Let’s say we need to compute the sum of the submatrix (startRow, startCol) -> (endRow, endCol), $S$. We can first pre-compute the sum of (0,0) -> (endRow, endCol) denote as $S_{1}$, the sum of (0,0) -> (endRow, startCol-1) denote as $S_{2}$, the sum of (0,0) -> (startRow-1, endCol) denote as $S_{3}$ and the sum of (0,0) -> (startRow-1, startCol-1) denote as $S_{4}$, then $S = S_{1} - S{2} - S{3} + S{4}$. Hence, we can pre-compute sums of (0,0) -> (i,j) for every pair of (i,j). Then we searching, the computation of sum of submatrix will only need a single operation.

Codes:

```	private static int[][] sums;

private static void preComputeSums(int[][] matrix) {
sums = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; ++i) {
for (int j = 0; j < matrix[i].length; ++j) {
if (i == 0 && j == 0)
sums[i][j] = matrix[i][j];
else if (j == 0)
sums[i][j] = sums[i - 1][j] + matrix[i][j];
else if (i == 0)
sums[i][j] = sums[i][j - 1] + matrix[i][j];
else
sums[i][j] = sums[i - 1][j] + sums[i][j - 1]
- sums[i - 1][j - 1] + matrix[i][j];
}
}
}

private static int computeSum(int[][] matrix, int startRow, int endRow,
int startCol, int endCol) {
if (startRow == 0 && startCol == 0)
return sums[endRow][endCol];
else if (startRow == 0)
return sums[endRow][endCol] - sums[endRow][startCol - 1];
else if (startCol == 0)
return sums[endRow][endCol] - sums[startRow - 1][endCol];
else
return sums[endRow][endCol] - sums[endRow][startCol - 1]
- sums[startRow - 1][endCol]
+ sums[startRow - 1][startCol - 1];
}

public static int[][] findSubmatrixWithMaxSum(int[][] matrix) {
preComputeSums(matrix);
int startRow = 0, endRow = 0;
int startCol = 0, endCol = 0;
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < matrix.length; ++i) {
for (int j = 0; j < matrix[i].length; ++j) {
for (int rowPtr = i; rowPtr < matrix.length; ++rowPtr) {
for (int colPtr = j;
colPtr < matrix[rowPtr].length; ++colPtr) {
int sum = computeSum(matrix, i, rowPtr, j, colPtr);
if (sum > maxSum) {
maxSum = sum;
startRow = i;
endRow = rowPtr;
startCol = j;
endCol = colPtr;
}
}
}
}
}

int[][] subMatrix = new int[endRow - startRow + 1][endCol - startCol
+ 1];
for (int i = startRow; i <= endRow; ++i)
System.arraycopy(matrix[i], startCol, subMatrix[i - startRow], 0,
endCol - startCol + 1);
return subMatrix;
}

__ATA.cmd.push(function() {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});