Problem overview
The method maxSum(int[][] grid) receives an m x n grid of integers, which can be negative, and returns the largest sum of any submatrix: a rectangle of adjacent cells, from one cell up to the whole grid.
In the example grid
1 -9 -10 1
-1 10 10 1
0 9 9 -9
-1 -1 -1 -1
the best rectangle is the 2 x 2 block of 10, 10, 9 and 9 in the middle, with sum 38. Extending it in any direction brings in negative numbers, such as the -9 and -10 above it, and lowers the total.
Approach: sum any rectangle in constant time
The brute-force way picks a rectangle and adds up its cells, which costs up to m * n additions for each of the many rectangles. This lesson removes that inner cost with a table of prefix sums.
Define partialSums[i][j] as the sum of all cells in the rectangle from (0, 0) to (i, j), both included. Once the table exists, the sum of any rectangle needs only four lookups, by inclusion and exclusion. To sum the rows x1..x2 and columns y1..y2, start with the big rectangle that reaches (x2, y2). It contains too much, so subtract the strip above row x1 and the strip left of column y1. Those two strips overlap in the top-left corner, which was subtracted twice, so add that corner back:
sum = P(x2, y2) - P(x1 - 1, y2) - P(x2, y1 - 1) + P(x1 - 1, y1 - 1)
For the example, rows 1 to 2 and columns 1 to 2: P(2, 2) = 19, P(0, 2) = -18, P(2, 0) = 0 and P(0, 0) = 1, so the sum is 19 + 18 - 0 + 1 = 38.
The table itself is built with the same idea. partialSums[i][j] is the cell plus the sum above it plus the sum to its left, minus the overlap of those two, the sum diagonally up-left. The helper get returns 0 for coordinates outside the grid, so the first row and column need no special cases: a missing neighbour simply counts as zero.
With O(1) rectangle sums, the program tries every rectangle: choose a top-left corner (x1, y1) and a bottom-right corner (x2, y2) with x2 >= x1 and y2 >= y1, compute its sum, and keep the maximum. This is the straightforward version; the lesson Maximum Sum Submatrix III on the same problem is the place to look for a different approach.
Step by step
- Start
resultatgrid[0][0]. One cell is a submatrix, so this is a real candidate. Starting at 0 would be wrong when every number is negative. - Allocate
partialSumswith the same dimensions as the grid. Java fills a newintarray with zeros. - Write
get(grid, i, j). It returnsgrid[i][j]when both indices are inside the grid and 0 otherwise. - Fill the table row by row with two nested loops. Each cell needs its upper and left neighbours, which are already filled when the loops go left to right, top to bottom.
- Choose the top-left corner with the loops over
x1andy1. - Choose the bottom-right corner with loops over
x2starting atx1andy2starting aty1, so the rectangle is never upside down. - Compute
sumwith the four-term formula, reading throughgetso thatx1 - 1ory1 - 1equal to -1 gives 0. - Update
resultwithMath.max(result, sum), and return it after the loops.
The solution in Java
class Solution {
int get(int[][] grid, int i, int j) {
if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length) {
return grid[i][j];
}
return 0;
}
public int maxSum(int[][] grid) {
int result = grid[0][0];
int[][] partialSums = new int[grid.length][grid[0].length];
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
partialSums[i][j] = grid[i][j] + get(partialSums, i - 1, j) +
get(partialSums, i, j - 1) -
get(partialSums, i - 1, j - 1);
}
}
for (int x1 = 0; x1 < grid.length; ++x1) {
for (int y1 = 0; y1 < grid[0].length; ++y1) {
for (int x2 = x1; x2 < grid.length; ++x2) {
for (int y2 = y1; y2 < grid[0].length; ++y2) {
int sum = get(partialSums, x2, y2) -
get(partialSums, x1 - 1, y2) -
get(partialSums, x2, y1 - 1) +
get(partialSums, x1 - 1, y1 - 1);
result = Math.max(result, sum);
}
}
}
}
return result;
}
};
Language details:
- 2D arrays are arrays of arrays.
grid.lengthis the number of rows andgrid[0].lengththe number of columns. The code assumes every row has the same length, and that the grid has at least one row and one column, since it readsgrid[0][0]first. - The helper reads from either array.
gettakes the array as a parameter, so the same method serves bothgridandpartialSums. - Short-circuit evaluation. In the bounds check,
&&stops at the first false part, sogrid[i][j]is only evaluated when the indices are valid. Reordering the conditions so that an array access comes first would throwArrayIndexOutOfBoundsException. - The semicolon after the class. The final
};is an empty declaration, which Java accepts. A bare}is the usual form.
Complexity
Building the table is O(m * n). The four nested loops visit every pair of corners; the number of rectangles in an m x n grid is about m^2 * n^2 / 4 and each costs O(1), so the time is O(m^2 * n^2) overall. For a 4 x 4 grid that is 100 rectangles; for a 100 x 100 grid it is about 25 million, which is fine, but 1000 x 1000 would be far too slow. The table needs O(m * n) extra space.
Edge cases and common mistakes
- All numbers negative. For
[[-3, -1], [-2, -5]]the answer is -1, the best single cell. This is whyresultstarts atgrid[0][0]and not 0. - A single cell.
[[5]]returns 5. - Forgetting to add the corner back. Subtracting both strips without adding
P(x1 - 1, y1 - 1)removes the overlap twice, and sums come out too small. - Indexing the table at -1. Writing
partialSums[x1 - 1][y2]directly throws forx1 = 0. Going throughgetavoids it. intoverflow. Sums areint, so very large values could wrap silently. Uselongif the numbers can be big.- Corners in the wrong order. Starting
x2ory2at 0 instead ofx1andy1would count "rectangles" that are inside out, which gives wrong sums.
Testing
Try the sample grid (38), [[5]] (5), [[-3, -1], [-2, -5]] (-1), and a one-row grid such as [[2, -1, 3]] (4, the whole row). The one-row case checks that the code works when there is only a single row of prefix sums.
