Maximal Rectangle

Given a binary matrix filled with 0's and 1's, find the area of the largest rectangle containing only 1's. The rectangle must be formed by contiguous cells with value 1. This problem requires you to compute the maximum area of a rectangle in the matrix that is entirely made up of 1's.

The efficient approach involves converting each row of the matrix into a histogram and then finding the largest rectangle area in that histogram using a stack-based method. The overall algorithm runs in O(n*m) time where n is the number of rows and m is the number of columns.

Note: All formulas in this description are provided in \( \LaTeX \) format. For example, if you denote the height of the histogram as \( h \) and width as \( w \), then the area can be computed as \( A = h \times w \).

inputFormat

The input is given via standard input (stdin) in the following format:

• The first line contains two integers \( n \) and \( m \), representing the number of rows and columns respectively.
• This is followed by \( n \) lines. Each line contains \( m \) space-separated integers (either 0 or 1) representing a row of the binary matrix.

outputFormat

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

4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

6