Problem overview
The method maxSum receives a grid of integers, grid, with n rows and m columns, and returns the largest sum of any subsquare: a block of cells with the same number of rows and columns. Values can be negative, so a bigger square is not always a better one.
In the example grid
1 -9 -10 1
-1 10 10 1
0 9 9 -9
-1 3 -1 -1the best subsquare is the 2x2 block [[10, 10], [9, 9]], whose sum is 38. A single cell is also a subsquare (1x1), which matters when every value is negative.
Approach: try every square, add up its cells
The simplest correct idea is to describe a square by two corners, the top-left cell (x1, y1) and the bottom-right cell (x2, y2), and try all pairs. A block is a square exactly when it spans the same number of rows and columns, that is, when x2 - x1 == y2 - y1. For each such pair, add up the cells in the block and keep the largest total.
This is a brute-force solution. It is easy to get right, and it is the baseline that the chapter's partial-sum technique improves: with prefix sums, the sum of any block is available in constant time instead of being recomputed cell by cell.
Step by step
- Write a helper that sums a block.
rectSumtakes the grid and both corners, and adds everygrid[x][y]withxfromx1tox2andyfromy1toy2, both ends included. - Read the dimensions.
nis the number of rows,len(grid), andmis the number of columns,len(grid[0]). - Start
resultwith a real answer. Setting it togrid[0][0], the sum of a valid 1x1 square, is safer than starting at 0. If every cell is negative, the answer is negative, and a starting value of 0 would wrongly beat it. - Choose the top-left corner with two loops over
x1andy1. - Choose the bottom-right corner with two more loops, starting at
x1andy1so that the corner is never above or to the left of the first one. - Keep only squares. Skip every pair where the height
x2 - x1differs from the widthy2 - y1. - Update the best sum with the larger of the current
resultand the block's sum. - Return
resultafter all the loops.
The solution in Go
type Solution struct {}
func (this Solution) rectSum(grid [][]int, x1, y1, x2, y2 int) int {
sum := 0
for x := x1; x <= x2; x++ {
for y := y1; y <= y2; y++ {
sum += grid[x][y]
}
}
return sum
}
func (this Solution) maxSum(grid [][]int) int {
n := len(grid)
m := len(grid[0])
result := grid[0][0]
for x1 := 0; x1 < n; x1++ {
for y1 := 0; y1 < m; y1++ {
for x2 := x1; x2 < n; x2++ {
for y2 := y1; y2 < m; y2++ {
if x2-x1 == y2-y1 {
result = max(result, this.rectSum(grid, x1, y1, x2, y2))
}
}
}
}
}
return result
}
The Go details worth a closer look:
- Methods on a struct. Go has no classes.
Solutionis an empty struct, andfunc (this Solution) maxSum(...)attaches a method to it. The part in parentheses is the receiver; here it is namedthis, and the code calls the other method asthis.rectSum(...). Go programmers usually pick a short name from the type, such ass, but any name works. - Grids are slices of slices.
[][]intis a slice whose elements are slices, one per row.len(grid)counts rows andlen(grid[0])counts the columns of the first row, so the code assumes the grid isn't empty. Rows can in principle have different lengths; the problem gives a rectangular grid. - The built-in
max. Since Go 1.21,maxis part of the language and accepts any ordered values, so no helper function ormathimport is needed. Older Go versions don't have it. - No parentheses, one loop keyword. Every loop here is a three-part
for. The condition has no parentheses, and the braces are required. - Short declarations.
:=declares and initialises a variable at once, and Go infers the type, sosumandresultareint. An unused variable is a compile error, which is why every name in the code is used.
Complexity
Let the grid be n x m, and let k be the smaller of the two.
Time. The four nested loops visit every pair of corners, about n² * m² pairs in the worst case, and the if keeps the ones that form squares. Each kept square of side s costs s² additions in rectSum. Counting the squares of each side, the total is on the order of n * m * k³, which is O(n⁵) for a square grid. That is fine for small grids and too slow for large ones.
Space: O(1). Besides the input, the code keeps a handful of integers.
The wasted work is visible: neighbouring squares share most of their cells, but rectSum adds them again from scratch each time. A prefix-sum table removes that repetition.
Edge cases and common mistakes
- All values negative. For
[[-5, -2], [-3, -4]]the answer is -2, the best single cell. Startingresultat 0 would return 0, which is not the sum of any subsquare. - A single cell.
[[-5]]returns -5. - Non-square grids. For a 2x3 grid, squares are at most 2x2. The loops handle this without extra code, because the end corner can never leave the grid.
- Exclusive end corners. The loops in
rectSumuse<=, because both corners belong to the block. Using<would drop the last row and column, and 1x1 squares would sum to 0. - Checking only the largest square. A bigger square can contain negative cells and lose to a smaller one. In
[[7, -20, 7], [-20, -20, -20]]the answer is 7, from a single cell.
Testing
- The example grid above gives
38. [[-5]]gives-5.[[-5, -2], [-3, -4]]gives-2.[[1, 2, 3], [4, 5, 6]]gives16, from the 2x2 block[[2, 3], [5, 6]].[[7, -20, 7], [-20, -20, -20]]gives7.