LESSON 244 OF 414 · PARTIAL SUMS #2

Maximum Sum Submatrix in Rust: Row Pairs and Kadane's Algorithm

Practice O(n² * m) Read the full explanation

Given a m x n grid filled with integers, find the submatrix with maximum sum among all submatrices.

Example:

Input:
[
  [ 1,  -9, -10,  1],
  [-1,  10,  10,  1],
  [ 0,   9,   9, -9],
  [-1,  -1,  -1, -1]
]
Output: 38
Explanation: Submatrix [[10, 10], [9, 9]]

STEP 1 OF 22

Guided

Ctrl + Enter to check

RUST · PARTIAL SUMS #2

Maximum Sum Submatrix in Rust, explained

Problem overview

The function max_sum receives a grid of integers, grid, as a Vec<Vec<i32>>, and returns the largest sum of any rectangular block of adjacent cells. Numbers can be negative, and a single cell counts as a block.

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 sum of the block [[10, 10], [9, 9]].

Approach: turn a rectangle into a subarray

A rectangle is a range of rows combined with a range of columns. Fix the range of rows, from a top row x1 to a bottom row x2, and squash it into one line: for each column, add up its cells between those two rows. The result is a one-dimensional array nums with one number per column.

Now a rectangle inside those rows is a run of consecutive entries of nums: picking columns y1 to y2 sums exactly nums[y1] + ... + nums[y2]. The best rectangle within these two rows is therefore the maximum subarray of nums, a problem with a linear-time solution (Kadane's algorithm).

Repeat that for every pair of rows (x1, x2) with x1 <= x2, and keep the best answer. For the example, rows 1 and 2 give the column sums [-1, 19, 19, -8]. The maximum subarray is 19 + 19 = 38.

Building nums by adding cells row by row for each pair would cost an extra factor of n. A table of column prefix sums avoids it: col_prefix[i][j] is the sum of column j from row 0 down to row i. The column sum between rows x1 and x2 is then col_prefix[x2][j] minus col_prefix[x1 - 1][j], in constant time. Compared with trying every pair of corners, this approach costs O(n² m) instead of O(n² m²).

Step by step

Store the sizes n (rows) and m (columns), then declare a mutable result for the best sum so far. Start it at grid[0][0], which is the sum of a real submatrix. Starting at 0 would fail when every number is negative.
Allocate col_prefix as an n by m table of zeros.
Visit every cell with i over the rows and j over the columns.
Copy the cell into col_prefix[i][j].
Add the cell above its prefix when i > 0, so the entry covers its whole column down to row i. Row 0 has nothing above it, which is why the check is needed.
Choose the top row x1 over all rows.
Choose the bottom row x2 from x1 to the last row.
Build nums with an iterator chain over the column indices 0..m that ends in collect(). The type annotation Vec<i32> tells collect what to build.
Map each column index y to that column's sum with a closure that has a block body.
Start the column sum at col_prefix[x2][y], the sum from row 0 to row x2.
Remove the rows above the top row by subtracting col_prefix[x1 - 1][y] when x1 > 0, and finish the closure with v as its value.
Combine with the best so far: result becomes the larger of itself and Self::max_subarray_sum(&nums), using the max method.
Return result as the tail expression after the loops.
Write max_subarray_sum for a slice. It keeps the best sum in result (starting at nums[0]) and the sum of the run ending at the current element in max_sum. For each val, max_sum becomes val + max_sum.max(0): a run with a negative sum can only hurt, so it is dropped (replaced by 0) before adding val. Then result is raised if needed.

The solution in Rust

impl Solution {
    fn max_subarray_sum(nums: &[i32]) -> i32 {
        let mut result = nums[0];
        let mut max_sum = 0i32;
        for &val in nums {
            max_sum = val + max_sum.max(0);
            result = result.max(max_sum);
        }
        result
    }

    fn max_sum(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let m = grid[0].len();
        let mut result = grid[0][0];

        // Column prefix sums: col_prefix[i][j] = sum of grid[0..=i][j]
        let mut col_prefix: Vec<Vec<i32>> = vec![vec![0; m]; n];
        for i in 0..n {
            for j in 0..m {
                col_prefix[i][j] = grid[i][j];
                if i > 0 {
                    col_prefix[i][j] += col_prefix[i - 1][j];
                }
            }
        }

        // Try all pairs of row boundaries
        for x1 in 0..n {
            for x2 in x1..n {
                let nums: Vec<i32> = (0..m)
                    .map(|y| {
                        let mut v = col_prefix[x2][y];
                        if x1 > 0 {
                            v -= col_prefix[x1 - 1][y];
                        }
                        v
                    })
                    .collect();
                result = result.max(Self::max_subarray_sum(&nums));
            }
        }
        result
    }
}

The Rust details worth a closer look:

Iterator chain. (0..m) is a range, which is an iterator. map turns each index into a sum, lazily, and collect() runs the chain and gathers the results into a Vec<i32>. The closure borrows col_prefix, x1 and x2 from the surrounding code.
Closure return value. The closure body is a block, and its last line, v with no semicolon, is the value for that column.
Guarding x1 - 1. x1 is a usize. When it is 0, x1 - 1 would wrap (in an optimized build) or panic (in a debug build), so the subtraction sits behind if x1 > 0. The same guard protects i - 1.
max is a method. result.max(x) returns the larger of two i32 values, so no if is needed.
Slices. The helper takes &[i32]. Passing &nums, a reference to a Vec<i32>, works because Rust converts it to a slice automatically.
for &val in nums. Iterating a &[i32] yields &i32; the &val pattern copies each number out of its reference.
Type inference. In vec![vec![0; m]; n] the literal 0 becomes an i32 because the variable is annotated as Vec<Vec<i32>>.

Complexity

Time: O(n² m). Building col_prefix is O(nm). There are about n² / 2 pairs of rows, and each pair costs O(m) to build nums and O(m) for the maximum subarray.

Space: O(nm). The table col_prefix is as large as the grid. Each nums vector has m entries and is dropped at the end of its pass. If the grid has fewer columns than rows, transposing it first would make the quadratic factor the smaller dimension.

Edge cases and common mistakes

All numbers negative. For [[-3, -1], [-2, -5]] the answer is -1. Both result in max_sum and the one in max_subarray_sum must start at a real value, not 0. The helper starts at nums[0], and the running sum max_sum is reset to val because max_sum.max(0) is 0 for a negative run.
A single cell. For [[5]] there is one pair of rows, nums is [5], and the answer is 5.
One row or one column. [[1, 2, 3]] gives 6 and [[2], [-1], [3]] gives 4. The second grid works because the pair of rows 0 and 2 produces nums = [4].
Starting x2 at 0. The bottom row must not be above the top row. Starting the inner loop at x1 keeps the ranges valid.
Forgetting to subtract. Without the x1 > 0 subtraction, the column sums would include rows above the chosen range.
Empty grid. Both grid[0] and nums[0] panic on empty input, so the function assumes at least one row and one column.
Overflow. Sums are i32. With optimizations they wrap silently on overflow.

Testing

The example grid gives 38.
[[-3, -1], [-2, -5]] gives -1.
[[-5, -5], [-5, -1]] gives -1.
[[5]] gives 5.
[[2], [-1], [3]] gives 4.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free