537. The Richest Rectangle
Find the rectangular submatrix with the largest total, and print that total. The rectangle must be non-empty. Values may be negative.
1 2 -1 -4 -20
-8 -3 4 2 1 -> 29
3 8 10 1 3
-4 -1 1 7 -6
The best rectangle there spans rows 1 to 3 and columns 1 to 3.
## Why this is not problem 535 with numbers
Problem 535 finds the largest all-ones rectangle, where every cell is equally good and the question is how far the ones extend. Here cells have values, negatives are allowed, and a rectangle can be worth extending THROUGH a bad row to reach a good one.
So there is nothing to grow incrementally, and the histogram reduction does not apply.
## Fix the rows, then run Kadane
Enumerate every pair of rows r1 <= r2. For that pair, collapse each column to the sum of
its entries between those rows:
col[c] = g[r1][c] + g[r1+1][c] + ... + g[r2][c]
Now a rectangle spanning exactly those rows is a contiguous RUN of col, and the best one
is the maximum-sum run, which is problem #57's single pass.
Every rectangle has exactly one top row and one bottom row, so enumerating the pair covers every rectangle once.
## Keeping the collapse incremental
Do not recompute col from scratch for each pair. Fix r1, start col at all zeros, and
ADD row r2 as r2 advances:
for r1 in 0..m-1:
col = [0] * n
for r2 in r1..m-1:
for c in 0..n-1: col[c] += g[r2][c]
run Kadane on col
That is O(m^2 n). Recomputing the sums instead gives O(m^3 n), and the fix is one line:
maintain the running column sums rather than rebuilding them.
## Kadane must allow all-negative
The rectangle is non-empty, so when every value is negative the answer is the single largest value, not 0.
cur = col[0]; best = col[0]
for c in 1..n-1: cur = max(col[c], cur + col[c]); best = max(best, cur)
Starting cur and best at 0 answers 0 on an all-negative grid, which is not achievable
by any non-empty rectangle. -1 -2 / -3 -4 answers -1 and is the test.
## Boundaries
0 0 / 0 0 answers 0, which is genuinely achievable here, so 0 as an answer is not by
itself evidence of the bug above.
2 -1 / -1 2 answers 2: the two positive cells are on a diagonal and no rectangle contains
both without also containing both negatives.
## Cost
Time O(m^2 n). Space O(n).
Put the SMALLER dimension on the squared axis by transposing when m > n, which costs
nothing and can matter a lot.
Constraints - `1 ≤ m ≤ 150` - `1 ≤ n ≤ 150` - `-1000 ≤ value ≤ 1000`
Input
The first line contains two integers m and n.
Each of the next m lines contains n integers.
Output
Print the largest total of any non-empty rectangular submatrix.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.