LESSON 217 OF 347 · PARTIAL SUMS #2

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

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 14

Guided

Ctrl + Enter to check

C# · PARTIAL SUMS #2

Maximum Sum Submatrix in C#, explained

Problem overview

The method MaxSum receives a rectangular grid of integers, int[,] grid, with m rows and n columns. It must return the largest sum among all submatrices, where a submatrix is a rectangle of adjacent rows and columns.

For the example grid below, the answer is 38, from the block 10, 10, 9, 9 in rows 1 and 2, columns 1 and 2.

 1  -9 -10   1
-1  10  10   1
 0   9   9  -9
-1  -1  -1  -1

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

The previous lesson on this problem tried every pair of corners with a two-dimensional prefix table, which costs O(m²n²). This lesson removes one dimension.

Suppose you decide on the top row x1 and the bottom row x2. Every submatrix between those rows is a stretch of columns. Add up each column between the two rows into one number, and you get a one-dimensional array nums of length n. Choosing a submatrix is now exactly choosing a contiguous subarray of nums, and its sum equals the submatrix sum. So for this pair of rows, the best submatrix is the maximum subarray sum of nums, which Kadane's algorithm finds in O(n).

Repeat that for every pair of rows. There are about m²/2 pairs, and each costs O(n) to build nums and O(n) to scan it, so the total is O(m²n).

Building nums quickly needs column prefix sums. columnPartialSums[i, j] is the sum of column j from row 0 down to row i. The column total between rows x1 and x2 is then columnPartialSums[x2, j] minus columnPartialSums[x1 - 1, j], the part above the top row.

Step by step

Start from a real value. result begins at grid[0, 0], since a single cell is a valid submatrix. Starting at 0 would be wrong for a grid of negative numbers.
Create the column table columnPartialSums, an int[,] of the same size as grid.
Fill it. Visit every cell in row order and copy grid[i, j]. If i > 0, also add the cell above in the table, which already holds everything higher up in that column. Row 0 has nothing above it.
Choose the rows. The outer loop picks the top row x1, and the next picks the bottom row x2, starting at x1 because the bottom can't be above the top.
Build the column totals. Create an int[] nums with one slot per column. For each column y, set nums[y] to columnPartialSums[x2, y], and when x1 > 0 subtract columnPartialSums[x1 - 1, y]. What remains is the column's sum over rows x1 to x2 only.
Solve the 1D problem. Call MaxSumSubarray(nums) and fold the result into result with Math.Max.
Return result.
Write MaxSumSubarray. It is Kadane's algorithm: the best subarray ending at the current element either extends the previous one, if that has a positive sum, or starts fresh. The running value is val + Math.Max(MaxSum, 0), and the overall best is updated each time.

The solution in C#

class Solution {

    public int MaxSumSubarray(int[] nums) {
        int result = nums[0];
        int MaxSum = 0;
        foreach (int val in nums) {
            MaxSum = val + Math.Max(MaxSum, 0);
            result = Math.Max(result, MaxSum);
        }
        return result;
    }

    public int MaxSum(int[,] grid) {
        int result = grid[0, 0];
        int[,] columnPartialSums = new int[grid.GetLength(0), grid.GetLength(1)];

        for (int i = 0; i < grid.GetLength(0); ++i) {
            for (int j = 0; j < grid.GetLength(1); ++j) {
                columnPartialSums[i, j] = grid[i, j];
                if (i > 0) {
                    columnPartialSums[i, j] += columnPartialSums[i - 1, j];
                }
            }
        }

        for (int x1 = 0; x1 < grid.GetLength(0); ++x1) {
            for (int x2 = x1; x2 < grid.GetLength(0); ++x2) {
                int[] nums = new int[grid.GetLength(1)];
                for (int y = 0; y < grid.GetLength(1); ++y) {
                    nums[y] = columnPartialSums[x2, y];
                    if (x1 > 0) {
                        nums[y] -= columnPartialSums[x1 - 1, y];
                    }
                }
                int sum = MaxSumSubarray(nums);
                result = Math.Max(result, sum);
            }
        }
        return result;
    }
};

C# details worth noticing

A local named like a method. Inside MaxSumSubarray, the variable MaxSum has the same name as the other method in the class. C# allows this, because a local variable and a method live in different declaration spaces, but it is confusing. Naming it current would be clearer.
foreach reads each element into val. You can't assign to the loop variable, which is fine here because the code only reads it.
Compound assignment. += and -= work on array elements, including elements of a rectangular array, as in nums[y] -= ....
Rectangular arrays. For an int[,], GetLength(0) gives the rows and GetLength(1) the columns. Length would give the total number of cells.

Complexity

Time: O(m²n). Building the column table is O(mn). There are about m²/2 row pairs, and each does O(n) work to build nums plus O(n) for Kadane's scan. Compared with O(m²n²), this saves a factor of n. If the grid is much wider than tall, you could transpose it first, so the pair of fixed lines is chosen along the shorter side.

Space: O(mn) for the column table, plus O(n) for nums.

Edge cases and common mistakes

All negative numbers. Both result in MaxSum and result in MaxSumSubarray start from an actual element, not 0. For a grid with rows -4, -2 and -7, -1, the answer is -1.
Kadane's reset. The code takes Math.Max(MaxSum, 0) before adding val. A negative running sum would only drag the next subarray down, so it is replaced by 0.
Forgetting the subtraction. Without the x1 > 0 subtraction, nums would hold sums from row 0 down to x2, not from x1 down to x2.
Sharing the array. A new nums is created for each row pair, so a stale value from the previous pair can't leak in. Every slot is overwritten anyway, but a fresh array makes that obvious.
Index -1. The check x1 > 0 avoids reading row -1, which would throw an IndexOutOfRangeException.

Testing

The 4 by 4 example grid returns 38.
A grid with rows -4, -2 and -7, -1 returns -1.

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