Problem overview
The method MaxSum receives a rectangular grid of integers, int[,] grid, with m rows and n columns. It must find the submatrix, a rectangle of adjacent rows and columns, with the largest sum, and return that sum.
In the example, the grid is:
1 -9 -10 1
-1 10 10 1
0 9 9 -9
-1 -1 -1 -1
The rectangle made of rows 1 and 2 and columns 1 and 2 contains 10, 10, 9, 9, which sums to 38. No other rectangle reaches that, so MaxSum returns 38.
Approach: constant-time rectangle sums
A rectangle is fixed by its top-left corner (x1, y1) and its bottom-right corner (x2, y2). There are about m²n²/4 of them. If adding up each rectangle took O(mn), the total would be far too slow. The trick is to make each rectangle's sum a constant-time lookup.
Define partialSums[i, j] as the sum of the rectangle from (0, 0) to (i, j). Each cell is built from three neighbours it overlaps with:
partialSums[i, j] = grid[i, j]
+ partialSums[i - 1, j]
+ partialSums[i, j - 1]
- partialSums[i - 1, j - 1]
The rectangles above and to the left both contain the region diagonally above-left of (i, j), so that region would be counted twice. Subtracting it once fixes this. This is inclusion-exclusion.
Running the same idea backwards gives any rectangle's sum from four lookups: take the big rectangle ending at (x2, y2), remove the rows above the submatrix and the columns to its left, and add back the corner that was removed twice.
Step by step
- Start the answer from a real value.
resultbegins atgrid[0, 0]. A single cell is itself a submatrix, so this is safe even when every number is negative, where starting at 0 would be wrong. - Create the prefix table.
partialSumsis anint[,]with the same dimensions asgrid, usingGetLength(0)for the rows andGetLength(1)for the columns. New cells are 0. - Write the helper
get. It returnsgrid[i, j]when(i, j)is inside the array, and 0 otherwise. The formulas look one row up or one column to the left, which at the edges would be index -1. The helper makes those cells count as 0 so that no special cases are needed. - Fill the table. Two nested loops go over every
(i, j)in row order. When a cell is computed, the cells above and to its left are already done. - Choose the top-left corner. The loops over
x1andy1cover every cell. - Choose the bottom-right corner.
x2starts atx1andy2starts aty1, since the bottom row can't be above the top row and the right column can't be left of the left column. - Compute the sum. Use the four-lookup formula: the sum up to
(x2, y2), minus the rows above, minus the columns to the left, plus the corner that was subtracted twice. - Keep the best with
Math.Maxand returnresultafter all the loops.
The solution in C#
class Solution {
public int get(int[,] grid, int i, int j) {
if (i >= 0 && i < grid.GetLength(0) && j >= 0 && j < grid.GetLength(1)) {
return grid[i, j];
}
return 0;
}
public int MaxSum(int[,] grid) {
int result = grid[0, 0];
int[,] partialSums = new int[grid.GetLength(0), grid.GetLength(1)];
for (int i = 0; i < grid.GetLength(0); ++i) {
for (int j = 0; j < grid.GetLength(1); ++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.GetLength(0); ++x1) {
for (int y1 = 0; y1 < grid.GetLength(1); ++y1) {
for (int x2 = x1; x2 < grid.GetLength(0); ++x2) {
for (int y2 = y1; y2 < grid.GetLength(1); ++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;
}
};
C# details worth noticing
- Rectangular arrays.
int[,]is a single block with fixed dimensions, indexed asgrid[i, j]. It is different from a jagged array,int[][], whose rows are separate arrays indexed asgrid[i][j]. GetLengthinstead ofLength. On a rectangular array,Lengthis the total count of cells, 16 for the 4 by 4 example.GetLength(0)is the number of rows andGetLength(1)the number of columns.- The helper is named
get. The lesson's own method uses a lowercase name. C# is case-sensitive, so the calls must match it exactly; the usual convention for public methods is PascalCase,Get. - Statements across lines. A long expression can continue on the next line. The statement ends at the semicolon, so a trailing
+or-at the end of a line is what tells the compiler to keep reading.
Complexity
Time: O(m²n²). Building the table costs O(mn). The four nested loops then visit every rectangle, and each takes constant time thanks to the table. For a 100 by 100 grid, that is on the order of 25 million rectangles.
Space: O(mn) for partialSums.
The next lesson on this problem reduces the time to O(m²n) by fixing only the top and bottom rows and solving a one-dimensional problem for the columns.
Edge cases and common mistakes
- All negative numbers. For a grid with
-4, -2in the first row and-7, -1in the second, the answer is-1, a single cell. Startingresultat 0 would return 0, which no submatrix gives. - Forgetting to subtract the diagonal. Without the
- get(partialSums, i - 1, j - 1)term, the overlapping region is counted twice and every sum is too large. - Index -1 at the edges. Reading
partialSums[x1 - 1, y2]directly whenx1is 0 throws anIndexOutOfRangeException. That is why every neighbour read goes throughget. - Looping to
GetLength(0) - 1. The conditions use<against the full length, not against length minus 1. - A single row or column. The code works unchanged, because the rectangle loops cover one-row and one-column rectangles.
Testing
- The 4 by 4 grid from the example returns
38. - A grid with rows
-4, -2and-7, -1returns-1.