Maximal Rectangle in a Binary Matrix

Given a binary matrix of size R × C, find the area of the largest rectangle containing only 1s.

You are provided with a matrix where each element is either 0 or 1. Your task is to determine the size of the largest rectangle (submatrix) that contains only 1s. The rectangle's area is defined as its number of cells.

The input is read from standard input (stdin) as follows:

• The first line contains two integers R and C, representing the number of rows and columns of the matrix respectively.
• The following R lines each contain C space-separated integers (0 or 1).

The output should be written to standard output (stdout) as a single integer that denotes the maximum area of the rectangle made up entirely of 1s.

A common efficient approach to solving this is to use histogram techniques where for each row you compute the heights of consecutive 1s and then use a stack-based method to compute the maximum area under that histogram. The area of a rectangle can be represented by the formula: $\text{Area} = \text{height} \times \text{width}$.

inputFormat

The input is given via stdin. The first line contains two space-separated integers R and C. Each of the next R lines contains C space-separated integers (either 0 or 1), representing the binary matrix.

outputFormat

Output a single integer to stdout – the area of the largest rectangle that contains only 1s.## sample

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

6