Maximum sum rectangle in a 2D matrix

The problem, simply

You get a grid of whole numbers with R rows and C columns. Some are negative. Choose a rectangle: a top row, a bottom row, a left column and a right column. Add up every number inside.

Give back the biggest total any rectangle can have. The rectangle must hold at least one cell, so if every number is negative, the answer is the least negative single number.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every rectangle, but make adding it up instant with a table of corner sums.

1. Build pre[i][j], the sum of everything above and to the left of cell (i, j), including the row and column before it.
2. The sum of rows t..b and columns l..r is pre[b+1][r+1] - pre[t][r+1] - pre[b+1][l] + pre[t][l].
3. Loop over all t <= b and all l <= r and keep the best.

class Solution {
    public int maxRectSum(int[][] g) {
        int R = g.length, C = g[0].length;
        int[][] pre = new int[R + 1][C + 1];              // corner sums with a zero border
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                pre[i + 1][j + 1] = g[i][j] + pre[i][j + 1] + pre[i + 1][j] - pre[i][j];

        int best = Integer.MIN_VALUE;
        for (int t = 0; t < R; t++)
            for (int b = t; b < R; b++)
                for (int l = 0; l < C; l++)
                    for (int r = l; r < C; r++) {
                        int sum = pre[b + 1][r + 1] - pre[t][r + 1] - pre[b + 1][l] + pre[t][l];
                        best = Math.max(best, sum);
                    }
        return best;
    }
}

How long it takes: about R^2 / 2 row pairs times C^2 / 2 column pairs, O(R^2 * C^2). Extra room: the corner sum table, O(R * C). Without that table, adding up each rectangle by hand would be O(R^3 * C^3).

Way 2: the clever way

Fix the left column left. Move the right column right one step at a time, and keep rowSum[i], the sum of row i from left to right. Each step only adds one new column to each row sum.

For each strip, run the best stretch trick on rowSum to find the best top and bottom rows:

1. cur is the best stretch ending at this row. It is max(rowSum[i], cur + rowSum[i]).
2. best is the biggest cur seen.

The animation runs every strip. The highlighted column band is the strip, and the bright rows are the best stretch inside it.

class Solution {
    public int maxRectSum(int[][] g) {
        int R = g.length, C = g[0].length;
        int best = Integer.MIN_VALUE;
        for (int left = 0; left < C; left++) {
            int[] rowSum = new int[R];                      // row sums for the strip left..right
            for (int right = left; right < C; right++) {
                for (int i = 0; i < R; i++) rowSum[i] += g[i][right];   // add one column
                best = Math.max(best, bestStretch(rowSum));
            }
        }
        return best;
    }

    private int bestStretch(int[] a) {                      // Kadane: biggest sum of a stretch
        int cur = a[0], best = a[0];
        for (int i = 1; i < a.length; i++) {
            cur = Math.max(a[i], cur + a[i]);               // carry on, or start fresh
            best = Math.max(best, cur);
        }
        return best;
    }
}

How long it takes: C^2 / 2 strips, and each strip costs O(R) to update and scan, so O(C^2 * R). Extra room: one rowSum array, O(R). If the grid has more columns than rows, loop over row pairs instead and squash columns, so the squared part is the smaller side: O(min(R,C)^2 * max(R,C)).

Watch out for

• Reset rowSum when left moves, not when right moves.
• Sums of many large numbers can overflow int. Use long if values can be big.
• To return the rectangle, remember left, right and the stretch's start and end rows whenever best improves.

What interviewers ask next

• Biggest rectangle with sum at most k (LeetCode 363)? Same strips, but for each strip use running sums and a sorted set to find the smallest earlier running sum that is at least current - k. That is O(C^2 * R log R).
• Largest rectangle with sum exactly 0? Same strips, and a hash map of running sums to find two equal ones.
• Biggest square instead of rectangle? Use the corner sum table and loop over the square size.
• Can it go below O(n^3) for an n by n grid? Only with heavy theory. In interviews O(n^3) is the expected answer.

Remember this

Grown-up words: the fence is a sub-matrix, the corner sum table is a 2D prefix sum, squashing a strip is column compression, and the best stretch trick is Kadane's algorithm, which is a tiny 1D DP.