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 ( of them) and compute their sums, keeping track of the curren maximum. Without additional optimization, the computation of sums cost , giving total a algorithm. We can precompute some sums to reduce the total costs to :

Let’s say we need to compute the sum of the submatrix (startRow, startCol) -> (endRow, endCol), . We can first pre-compute the sum of (0,0) -> (endRow, endCol) denote as , the sum of (0,0) -> (endRow, startCol-1) denote as , the sum of (0,0) -> (startRow-1, endCol) denote as and the sum of (0,0) -> (startRow-1, startCol-1) denote as , then . 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; }