Problem overview
The function max_sum receives a grid of integers, grid, as a Vec<Vec<i32>> with n rows and m columns. It must return the largest sum of a subsquare: a block of adjacent cells with the same number of rows as columns. A single cell is a 1x1 subsquare. The numbers may be negative.
In the example the grid is
1 -9 -10 1
-1 10 10 1
0 9 9 -9
-1 3 -1 -1
The answer is 38, from the 2x2 block [[10, 10], [9, 9]].
Approach: try every block, keep the squares
A block is fixed by its top-left corner (x1, y1) and its bottom-right corner (x2, y2). It has x2 - x1 + 1 rows and y2 - y1 + 1 columns, so it is a square exactly when x2 - x1 == y2 - y1.
The brute-force idea is just that: loop over all four coordinates, skip every pair of corners that doesn't describe a square, add up the cells of each square, and keep the maximum. It is the simplest correct solution, and it is the right place to start: every faster method for this problem computes the same sums in a cleverer way, and its answers are easy to compare against this one.
For the example, the 2x2 block starting at row 1, column 1 has corners (1, 1) and (2, 2). Both differences are 1, so it is a square, and its sum is 10 + 10 + 9 + 9 = 38. No other square is larger. The whole grid is a 4x4 square with a much smaller sum.
Step by step
- Write a helper,
rect_sum, that adds up the cells between two corners. It takes the grid by reference and the four coordinates asusize. - Start the sum at 0 and loop over the rows
x1..=x2and, inside, the columnsy1..=y2. Both ranges are inclusive, because the corners belong to the block. Add each cell and return the total. - Read the size of the grid in
max_sum:nrows andmcolumns. - Start
resultatgrid[0][0]. That cell is a 1x1 subsquare, so it is a real candidate. Starting at 0 would be wrong when every number is negative. - Choose the top-left corner with
x1over all rows andy1over all columns. - Choose the bottom-right corner with
x2fromx1to the last row andy2fromy1to the last column. The corner can't be above or to the left of the first one. - Keep only squares: test
x2 - x1 == y2 - y1. - Update the answer with the larger of
resultand the block's sum. - Return
resultafter the loops, with no semicolon.
The solution in Rust
impl Solution {
fn rect_sum(grid: &Vec<Vec<i32>>, x1: usize, y1: usize, x2: usize, y2: usize) -> i32 {
let mut sum = 0i32;
for x in x1..=x2 {
for y in y1..=y2 {
sum += grid[x][y];
}
}
sum
}
fn max_sum(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
let m = grid[0].len();
let mut result = grid[0][0];
for x1 in 0..n {
for y1 in 0..m {
for x2 in x1..n {
for y2 in y1..m {
if x2 - x1 == y2 - y1 {
result = result.max(Self::rect_sum(&grid, x1, y1, x2, y2));
}
}
}
}
}
result
}
}
The Rust details worth a closer look:
- Inclusive and exclusive ranges.
a..bstops beforeb, anda..=bincludes it. The helper uses..=because the second corner is part of the block. The loops inmax_sumuse..nbecausenis a length, not an index. - Unsigned subtraction is safe here.
x2 - x1andy2 - y1areusizevalues, which can't go below zero. The loops guaranteex2 >= x1andy2 >= y1, so the subtraction never underflows. Withx1 - x2the code would wrap in an optimized build and panic in a debug build. - Borrowing. The helper takes
&Vec<Vec<i32>>, a shared reference, so each call reads the grid without moving or copying it.Self::rect_sum(&grid, ...)passes the borrow. - The
0i32suffix. It makes the sum ani32, the same type as the cells. maxas a method.result.max(x)returns the larger of two integers.- Tail expressions.
sumandresulthave no semicolon, so they are the returned values. - Overflow. The lessons build with optimizations, so an
i32sum that overflows wraps silently. A debug build would panic. The code assumes sums that fit in ani32.
Complexity
Time. The four loops visit up to about n² m² / 4 pairs of corners, and each qualifying square of side k costs k² additions in rect_sum. For an n by n grid the total is O(n⁵): there are roughly (n - k + 1)² squares of side k, and summing (n - k + 1)² · k² over k gives a constant times n⁵. That is fine for small grids and far too slow for large ones.
Space: O(1). The function keeps a few integers and borrows the grid.
Two improvements are available. Precomputed 2D prefix sums make each block sum O(1), which lowers the time to the number of pairs of corners. And instead of testing every pair of corners for squareness, choosing a corner and a side length visits only squares.
Edge cases and common mistakes
- All numbers negative. For
[[-3, -1], [-2, -5]]the answer is -1, the best single cell. Initializingresultwith 0 would return 0, a sum no square has. - A single cell. For
[[7]]the answer is 7. - Non-square grids. For a 2x3 grid like
[[1, 2, 3], [4, 5, 6]], only 1x1 and 2x2 squares exist. The answer is 16, from the 2x2 block on the right. The side can never exceed the smaller dimension, which the corner test enforces automatically. - The whole grid as the answer. For
[[-1, 5], [5, -1]]the 2x2 square sums to 8, larger than any single cell. - Rectangles are not squares. A 1x3 block can have a higher sum than any square. Dropping the
x2 - x1 == y2 - y1test solves a different problem, the maximum sum submatrix. - Off-by-one on the side. The side is
x2 - x1 + 1, but the test compares differences, so the+ 1cancels on both sides. A test likex2 - x1 == y2 - y1 + 1would accept blocks that aren't square. - Empty grid.
grid[0]panics on an empty vector, so the function assumes at least one row and one column.
Testing
- The example grid gives 38.
[[-3, -1], [-2, -5]]gives -1.[[1, 2, 3], [4, 5, 6]]gives 16.[[-1, 5], [5, -1]]gives 8.[[1, -1, 1], [-1, 1, -1], [1, -1, 9]]gives 9.
