Maximal Rectangle Area in a Binary Grid

This problem asks you to determine the area of the largest rectangle within a binary grid that is entirely composed of '1's. Each cell in the grid is either '0' (inactive) or '1' (active). The goal is to compute the maximum area of a rectangular subgrid that contains only active cells.

A common approach is to use a histogram-based algorithm. For each row, treat the sequence of values as histogram bar heights where each bar represents the number of consecutive '1's up to that row. Then, you can use a stack-based method to compute the largest rectangle in the histogram in O(n) time.

The area of a rectangle is computed using the formula: \[ \text{area} = \text{height} \times \text{width} \] where the width is determined by the difference between indices in the histogram.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(n\) which represents the number of rows in the grid. This is followed by \(n\) lines, each containing a string comprised of characters '0' and '1' of equal length, representing each row of the grid.

outputFormat

Output a single integer to standard output (stdout), which is the area of the largest rectangle that contains only '1's.

4
1010
1011
1111
0011

6