Start learning free

LESSON 236 OF 409 · PARTIAL SUMS #2

Maximum Sum Submatrix in C++: Column Sums and Kadane in O(m²n)

Practice O(n2 * 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 20
    Ctrl + Enter to check

    C++ · PARTIAL SUMS #2

    Maximum Sum Submatrix in C++, explained

    Problem overview

    The method maxSum(vector<vector<int>>& grid) receives an m x n grid of integers, which may be negative, and returns the largest sum over all submatrices. A submatrix is a block of consecutive rows and consecutive columns, and it must contain at least one cell.

    In the example grid

    [ 1,  -9, -10,  1]
[-1,  10,  10,  1]
[ 0,   9,   9, -9]
[-1,  -1,  -1, -1]

    the best block is the 2x2 square [[10, 10], [9, 9]] in rows 1 and 2, columns 1 and 2. Its sum is 38.

    Approach: fix two rows, then solve a 1D problem

    Checking every submatrix directly is slow: there are about m²n²/4 of them, and summing each takes up to m·n more steps. Two ideas bring the cost down.

    First, fix the top row x1 and the bottom row x2. A submatrix between those rows takes some range of columns. If you add up each column over the rows x1 to x2, you get one array nums with n numbers, and the sum of a submatrix on columns a to b is the sum of nums[a..b]. So the best submatrix for these two rows is the best subarray of nums.

    Second, find the best subarray with Kadane's algorithm in O(n). It keeps the best sum of a subarray ending at the current element: if the running sum before the element is negative, drop it and restart from the element alone.

    Building nums naively for every pair of rows would cost O(m·n) per pair. A table of column partial sums fixes that. Let columnPartialSums[i][j] be the sum of column j from row 0 down to row i. The sum of column j over rows x1 to x2 is then columnPartialSums[x2][j] - columnPartialSums[x1 - 1][j] (just the first term when x1 is 0), which is a single subtraction.

    For rows 1 and 2 of the example, the column sums are nums = [-1, 19, 19, -8]. The best subarray is 19 + 19 = 38, which matches the answer.

    Step by step

    1. Start result at a real submatrix sum. It is grid[0][0], a single cell. Starting at 0 would be wrong when every cell is negative.
    2. Allocate columnPartialSums with the same shape as the grid: grid.size() rows of grid[0].size() zeros each.
    3. Fill it row by row. Copy grid[i][j], then, if i > 0, add the entry above, columnPartialSums[i - 1][j].
    4. Choose the top row x1 from 0 to the last row.
    5. Choose the bottom row x2 from x1 to the last row.
    6. Build nums. For every column y, set nums[y] to columnPartialSums[x2][y], and when x1 > 0 subtract columnPartialSums[x1 - 1][y].
    7. Solve the 1D problem. maxSumSubarray(nums) returns the best subarray sum, and result becomes the larger of the two.
    8. Return result.
    9. Write maxSumSubarray. It starts result at nums[0] and the running sum maxSum at 0. For each val, maxSum = val + max(maxSum, 0) either extends the previous run or restarts at val, and result keeps the largest maxSum.

    The solution in C++

    class Solution {
public:
    int maxSumSubarray(vector<int> &nums) {
        int result = nums[0];
        int maxSum = 0;
        for (int val : nums) {
            maxSum = val + max(maxSum, 0);
            result = max(result, maxSum);
        }
        return result;
    }

    int maxSum(vector<vector<int>> &grid) {
        int result = grid[0][0];
        vector<vector<int>> columnPartialSums(grid.size(),
                                              vector<int>(grid[0].size()));
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                columnPartialSums[i][j] = grid[i][j];
                if (i > 0) {
                    columnPartialSums[i][j] += columnPartialSums[i - 1][j];
                }
            }
        }

        for (int x1 = 0; x1 < grid.size(); ++x1) {
            for (int x2 = x1; x2 < grid.size(); ++x2) {
                vector<int> nums(grid[0].size());
                for (int y = 0; y < grid[0].size(); ++y) {
                    nums[y] = columnPartialSums[x2][y];
                    if (x1 > 0) {
                        nums[y] -= columnPartialSums[x1 - 1][y];
                    }
                }
                int sum = maxSumSubarray(nums);
                result = max(result, sum);
            }
        }
        return result;
    }
};

    The C++ details:

    • Nested vectors. vector<vector<int>>(rows, vector<int>(cols)) builds rows copies of a zero-filled row. The closing >> is fine since C++11. Rows can differ in length in principle, but here every row is as long as grid[0].
    • References as parameters. vector<int> &nums and vector<vector<int>> &grid avoid copying the data on every call. maxSumSubarray is called once per pair of rows, so copying would add O(n) work each time.
    • Signed and unsigned. grid.size() is unsigned, and the loops compare it with int indices. That is safe because the indices start at 0 and only grow.
    • Integer overflow. All sums are int. If the grid is large and the values are big, a sum can exceed about 2.1 billion, and signed overflow is undefined behaviour. Use long long if the limits require it.

    Complexity

    Let the grid have m rows and n columns.

    Time: O(m²·n). Building the partial sums costs O(m·n). There are about m²/2 pairs of rows, and each pair costs O(n) to build nums and O(n) for Kadane. Choosing the smaller dimension as the one you pair up (transpose if m > n) makes this O(min(m,n)² · max(m,n)).

    Space: O(m·n) for the partial-sum table, plus O(n) for nums.

    Edge cases and common mistakes

    • All cells negative. For [[-3, -1], [-2, -5]] the answer is -1, the single largest cell. Both result variables start at an actual value (grid[0][0] and nums[0]) rather than 0, so this works. In maxSumSubarray, maxSum itself starts at 0, but that is just the sum of an empty run before the first element.
    • A single cell. [[-4]] gives -4.
    • A single row or column. A one-row grid has only the pair x1 = x2 = 0, and the algorithm reduces to Kadane on that row.
    • Forgetting the x1 > 0 check. Reading columnPartialSums[x1 - 1] with x1 = 0 is an index of -1, which is out of bounds.
    • Restricting x2 to start after x1. Single-row submatrices need x2 = x1, so the loop starts at x1, not x1 + 1.
    • Using an empty submatrix. Initializing result to 0 effectively allows an empty block, which is not a valid answer when all numbers are negative.

    Testing

    • The example grid above gives 38.
    • [[-3, -1], [-2, -5]] gives -1.
    • [[-4]] gives -4.
    • [[1, 2, 3]] gives 6.
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free