Problem overview
The function max_sum receives a grid of integers, grid, as a Vec<Vec<i32>>. It must return the largest sum that any rectangular block of adjacent cells can have. The block can be a single cell, a row segment, a column segment or any rectangle, and the numbers can be negative.
In the example the grid is
1 -9 -10 1
-1 10 10 1
0 9 9 -9
-1 -1 -1 -1
and the answer is 38. The block made of the rows 1 and 2 and the columns 1 and 2 holds 10, 10, 9 and 9. No other rectangle does better.
Approach: sum any rectangle in constant time
A rectangle is fixed by two corners: the top-left one (x1, y1) and the bottom-right one (x2, y2). A grid with n rows and m columns has about n² m² / 4 rectangles, so checking them all is only cheap if each rectangle's sum costs O(1). Adding up its cells every time would cost up to O(nm) more, for O(n³ m³) overall.
The tool for that is a 2D prefix sum. Let partial[i][j] be the sum of the whole rectangle from (0, 0) to (i, j). Two rules do the work.
- Building it:
partial[i][j]is the cell, plus the prefix above it, plus the prefix to its left, minus the prefix diagonally above-left. The top and left prefixes both contain the diagonal one, so it was counted twice and must be removed once. - Using it: the sum of the rectangle from
(x1, y1)to(x2, y2)ispartial[x2][y2], minus the rows above the rectangle, minus the columns to its left, plus back the corner that both subtractions removed.
With that, the solution tries every pair of corners, computes each sum with four lookups and keeps the maximum. The lesson trades speed for simplicity: it is O(n² m²), which a later lesson on the same problem improves.
Step by step
- Store the sizes.
nis the number of rows andmthe number of columns, taken fromgrid.len()andgrid[0].len(). - Start
resultatgrid[0][0]. A single cell is a valid rectangle, so this is a real sum. Starting at 0 would be wrong when every number is negative, because the best rectangle then has a negative sum. - Allocate
partialasnrows ofmzeros. The0i32literal fixes the element type. - Loop over every cell
(i, j), rows outside and columns inside. - Write the helper
getfirst, because the formulas need to read "one row up" or "one column left" even at the border. It returns the grid value at(i, j), or 0 when the position is outside the grid. Its indices arei32because callers pass -1. - Fill
partial[i][j]with the cell plus the prefix above, plus the prefix to the left, minus the diagonal prefix. Outside the grid,getsupplies 0, so the first row and column need no special code. - Choose the top-left corner with
x1over the rows andy1over the columns. - Choose the bottom-right corner with
x2fromx1to the last row andy2fromy1to the last column. The bottom edge can't be above the top edge, and the right edge can't be left of the left edge. - Compute
sumfrom the four prefix values, usinggetagain so that a rectangle touching the top or left border subtracts 0. - Keep the larger value in
result, and return it after all the loops.
The solution in Rust
impl Solution {
fn get(grid: &Vec<Vec<i32>>, i: i32, j: i32) -> i32 {
if i >= 0 && i < grid.len() as i32 && j >= 0 && j < grid[0].len() as i32 {
return grid[i as usize][j as usize];
}
0
}
fn max_sum(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
let m = grid[0].len();
let mut result = grid[0][0];
let mut partial = vec![vec![0i32; m]; n];
for i in 0..n {
for j in 0..m {
partial[i][j] = grid[i][j]
+ Self::get(&partial, i as i32 - 1, j as i32)
+ Self::get(&partial, i as i32, j as i32 - 1)
- Self::get(&partial, i as i32 - 1, j as i32 - 1);
}
}
for x1 in 0..n {
for y1 in 0..m {
for x2 in x1..n {
for y2 in y1..m {
let sum = Self::get(&partial, x2 as i32, y2 as i32)
- Self::get(&partial, x1 as i32 - 1, y2 as i32)
- Self::get(&partial, x2 as i32, y1 as i32 - 1)
+ Self::get(&partial, x1 as i32 - 1, y1 as i32 - 1);
if sum > result {
result = sum;
}
}
}
}
}
result
}
}
The Rust details worth a closer look:
- Why
gettakesi32. The loop variables areusize, which can't hold -1: in an optimized build0usize - 1wraps to a huge number, and in a debug build it panics. Casting withas i32first makesi as i32 - 1a safe -1, andgetturns it into 0. - Precedence of
as.asbinds tighter than-, soi as i32 - 1means(i as i32) - 1. - Casting back to index. Vectors are indexed with
usize. Once the bounds check has shown thatiandjare not negative,i as usizeis safe. - Borrowing.
Self::get(&partial, ...)only reads, so a shared borrow is enough. The call sits inside the assignmentpartial[i][j] = ..., which is fine because the borrow ends before the assignment happens. vec![vec![0i32; m]; n]. The inner vector is clonedntimes, so each row is independent.- Multi-line expressions. A line that starts with
+or-continues the previous one, since the statement ends only at the semicolon. - Tail expressions. The final
0ingetandresultinmax_sumhave no semicolon, so they are the returned values.
Complexity
Time: O(n² m²). Building partial takes O(nm). The four nested loops choose a pair of corners, which is up to about n² m² / 4 pairs, and each pair costs a constant number of lookups.
Space: O(nm). The table partial has the same size as the grid.
Edge cases and common mistakes
- All numbers negative. For
[[-3, -1], [-2, -5]]the answer is -1, the largest single cell. Initializingresultwith 0 would return 0, which no rectangle has. - A single cell. For
[[5]]the loops each run once and the answer is 5. - One row or one column.
[[1, 2, 3]]gives 6, and[[2], [-1], [3]]gives 4. The same code covers both, sincegetreturns 0 above the first row. - Forgetting the added-back corner. Subtracting the rows above and the columns to the left removes the overlap twice. The fourth term of
sumrestores it. - Looping from 0 instead of from the first corner. If
x2ory2started belowx1ory1, the formula would describe a rectangle that doesn't exist. - Empty grid.
grid[0]panics on an empty vector, so the function assumes at least one row and one column. - Overflow. Sums are
i32. With optimizations they wrap silently on overflow, so very large grids of large numbers would needi64.
Testing
- The example grid gives 38.
[[-3, -1], [-2, -5]]gives -1.[[5]]gives 5.[[1, 2, 3]]gives 6.[[2], [-1], [3]]gives 4.
