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

Advertisements

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

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

(function(){var c=function(){var a=document.getElementById("crt-1836354145");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:388248,containerid:"crt-1836354145",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();

(function(){var c=function(){var a=document.getElementById("crt-569776839");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:837497,containerid:"crt-569776839",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();

Like this:Like Loading...

Related
```