← All coding problems
Largest Rectangle of 1s
hardMatrix+40 XPTime limit 2s
The grid contains only 0s and 1s. Find the area of the largest rectangle (sides parallel to the grid) that contains only 1s.
Input:
- line 1:
r c - next
rlines:cvalues, each0or1
Output: the largest area (0 if the grid has no 1).
Constraints: 1 ≤ r, c ≤ 400.
Think about it: process the grid row by row. For each column keep the height of the run of 1s ending at the current row — together these heights form a histogram. The answer is the largest rectangle in any of these r histograms, which a monotonic stack finds in O(c) per row, O(r·c) in total.
Sample input 1
4 5 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
Sample output 1
6
Sample input 2
1 1 0
Sample output 2
0
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).