Problem overview
MaxSum receives a rectangular grid of integers, int[,] grid, and returns the largest sum of any subsquare: a block of cells with the same number of rows and columns. The grid itself doesn't have to be square, and the values may be negative.
In the example grid, the best subsquare is the 2x2 block in rows 1 and 2, columns 1 and 2: 10 + 10 + 9 + 9 = 38. A 1x1 square is a subsquare too, so a grid of only negative numbers returns its largest single cell. For {{-5, -2}, {-3, -4}} the answer is -2, not 0.
Approach
The simplest idea is to try every square and add up its cells. A square is fixed by its top-left corner (x1, y1) and its bottom-right corner (x2, y2). It is a square exactly when the height equals the width, which means x2 - x1 == y2 - y1.
So the solution enumerates every pair of corners, skips the pairs that aren't squares, and sums the cells of the others with a helper, RectSum. It keeps the maximum seen. This is a brute force, and it is the right starting point: it is easy to check, and later lessons in this chapter speed it up with partial sums.
Since the lesson is about partial sums, notice what is wasteful. RectSum re-adds the same cells again and again for overlapping squares. A table of prefix sums would give any rectangle sum in constant time, but this lesson doesn't use one.
To see the enumeration at work, take the example's top-left cell (0, 0). Its candidate bottom-right corners are every (x2, y2) in the grid, but only (0, 0), (1, 1), (2, 2) and (3, 3) have equal height and width, so those are the squares starting there: 1x1, 2x2, 3x3 and 4x4. The same filter applies to every other starting cell, and squares near the right or bottom edge get fewer options because they run out of room.
Step by step
- Write
RectSum. It receives the grid and two corners and addsgrid[x, y]for everyxfromx1tox2and everyyfromy1toy2, both inclusive. - Read the dimensions with
grid.GetLength(0)for the rows (n) andgrid.GetLength(1)for the columns (m). - Seed
resultwithgrid[0, 0], a real square sum, rather than 0. A starting value of 0 would be wrong when every cell is negative. - Loop over the top-left corner,
x1andy1, across the whole grid. - Loop over the bottom-right corner,
x2fromx1andy2fromy1, so the corner is never above or left of the start. - Keep only squares by testing
x2 - x1 == y2 - y1. - Update the maximum with
Math.Maxand the square's sum, then returnresultafter the loops.
The solution in C#
class Solution {
public int RectSum(int[,] grid, int x1, int y1, int x2, int y2) {
int sum = 0;
for (int x = x1; x <= x2; ++x) {
for (int y = y1; y <= y2; ++y) {
sum += grid[x, y];
}
}
return sum;
}
public int MaxSum(int[,] grid) {
int n = grid.GetLength(0);
int m = grid.GetLength(1);
int result = grid[0, 0];
for (int x1 = 0; x1 < n; ++x1) {
for (int y1 = 0; y1 < m; ++y1) {
for (int x2 = x1; x2 < n; ++x2) {
for (int y2 = y1; y2 < m; ++y2) {
if (x2 - x1 == y2 - y1) {
result = Math.Max(result, RectSum(grid, x1, y1, x2, y2));
}
}
}
}
}
return result;
}
}
C# details worth knowing:
int[,]is a rectangular array, not an array of arrays. It is one block of memory with two dimensions, indexed asgrid[x, y]. Writinggrid[x][y]doesn't compile for it. That form belongs to jagged arrays,int[][], where each row is a separate array.GetLength(dimension)gives the size of one dimension.grid.Lengthwould be the total number of cells,n * m, which is not what the loops need.- Literal syntax. You can build the example's small grid with
new int[,] { { 1, 2 }, { 3, 4 } }. - Whole-number arithmetic. The
intsums wrap around silently if they get too large, since C# doesn't checkintoverflow by default. Typical lesson inputs stay far from that.
Complexity
Time. The four nested loops visit up to about n²m²/4 corner pairs. For each pair that is a square of side s, RectSum adds s² cells. A grid with k = min(n, m) has roughly n·m·k squares, each costing up to O(k²) to sum, so the total is O(n²m² + n·m·k³). For an n x n grid this is O(n⁵), which grows fast: the cell additions alone for a 100 x 100 grid come to hundreds of millions.
Space: O(1). Only a few integers are stored beyond the input grid.
Edge cases and common mistakes
- All-negative grids. Start with
grid[0, 0], not 0, or the function returns a sum that no square has. - A single row or column. The only squares are 1x1 cells. For
{{1, 2, 3}}the answer is 3. - Mixing up the dimensions. The first index runs over rows and goes up to
GetLength(0), the second over columns. Swapping them reads outside the array and throwsIndexOutOfRangeExceptionon non-square grids. - Using
<instead of<=inRectSum. The corners are inclusive. With<, a 1x1 square would sum zero cells. - Accepting any rectangle. Without the
x2 - x1 == y2 - y1test, the loops would find the best rectangle, which can differ from the best square. A wide block of large positive numbers could then beat every square.
Testing
- The example grid gives
38. {{-5, -2}, {-3, -4}}gives-2.{{1, 2, 3}}gives3.