The Largest Rectangle of Ones
Find the largest rectangular submatrix consisting entirely of 1s, and print its AREA.
The rectangle need not be square.
1 0 1 0 0
1 0 1 1 1 -> 6 the 2 by 3 block in the lower right
1 1 1 1 1
1 0 0 1 0
## Why problem 534's trick does not extend
For SQUARES, one number per cell is enough: the side length of the largest square ending there. Rectangles have two independent dimensions, and no single number per cell determines the best rectangle ending there, because a short wide rectangle and a tall narrow one are not comparable.
So the state has to change rather than the recurrence.
## Reduce each row to a histogram
For each row, let heights[c] be the number of consecutive 1s ending at this row in
column c:
g[r][c] == 1 -> heights[c] += 1
otherwise -> heights[c] = 0
Every all-ones rectangle whose BOTTOM edge lies on row r is a rectangle inside that
histogram, and conversely. So the problem becomes: the largest rectangle in a histogram,
solved once per row.
Reducing a two-dimensional question to m copies of a one-dimensional one is the move, and
it is worth recognising by its shape: a quantity that can be maintained incrementally per
row, plus a known 1D subroutine.
## The histogram, with a monotonic stack
For each bar, the largest rectangle with that bar as its shortest one extends left until a strictly lower bar and right until a strictly lower bar.
A stack holding indices of increasing heights finds both boundaries in one pass: when a bar lower than the stack top arrives, the top is popped, and the popped bar's rectangle extends from just after the new top to just before the current position.
Pushing a sentinel of height 0 at the end flushes everything left on the stack, which removes a second loop.
## The width after popping
left = (stack top after popping) + 1, or 0 if the stack is empty
width = current index - left
Using the popped index rather than the new stack top is the classic error, and it
undercounts whenever several equal-height bars sit together. 1 1 / 1 1 answers 4 and
catches it.
## Cost
Time O(m n): each row builds its histogram in O(n) and each index is pushed and popped
at most once. Space O(n).
A cubic enumeration of every corner pair is O(m^2 n^2) and is the right thing to state
first before improving it.