## Problem Statement

Given a matrix with only binary values, find the area of the largest rectangle possible with all 1s.

### Input

```
Enter Number of Rows in the matrix: 4
Enter Number of Columns in the matrix: 5
Enter the matrix values:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
```

### Output

`Area of the largest matrix with all 1s: 6`

### Explanation

In the figure given below, the largest rectangle with all 1s is indicated as orange.

Also Read, __Byte Array to String__

## Approach

Letâ€™s assume the number of rows in the given matrix to be â€˜Râ€™. Similarly, assume the number of columns to be â€˜Câ€™. Consider the matrix given as input in the Problem Statement. The matrix can be divided into 1 to â€˜Râ€™ rows. Refer to the image given below for illustration.

Letâ€™s take the first row of the matrix. Assume every cell with value 1 as the bar with height 1. Similarly, Assume every cell with the value 0 as the bar with height 0. So, the first row can be converted to the histogram like the figure given below. As you can see here, the area of the largest rectangle with all 1s is 1.

We must know how to find the area of the largest rectangle in a histogram to solve the given problem. You can practice finding the area of the largest rectangle in a histogram on our practice platform at __Largest rectangle in a histogram__. If you canâ€™t figure out the solution, refer to the __The Largest Rectangular Area in Histogram__ blog to learn how to find the area of the largest rectangle in a histogram.

Now, add the 2nd row to the histogram. Letâ€™s call the first-row â€˜PREVIOUS_ROWâ€™. Similarly, 2nd row will be called â€˜CURRENT_ROWâ€™. The row created by using â€˜PREVIOUS_ROWâ€™ and â€˜CURRENT_ROWâ€™ will be called â€˜RESULTANT_ROWâ€™. The values of cells of the â€˜RESULTANT_ROWâ€™ are given according to the instructions given below.

- If the current column in â€˜CURRENT_ROWâ€™ is not 0, add the values of the cells of â€˜PREVIOUS_ROWâ€™ and â€˜CURRENT_ROWâ€™. Store the result into the â€˜RESULTANT_ROWâ€™.

- If the current cell in the â€˜CURRENT_ROWâ€™ is 0, assign the value of 0 to the â€˜RESULTANT_ROWâ€™.

Refer to the figure given below for a clear understanding of the instructions.

The resultant histogram created using the values of â€˜RESULTANT_ROWâ€™ will look like the figure given below.

Similarly, all the rows can be added to create the resultant histograms for all the cumulative rows. At any row, if the histogram has the area of the largest rectangle encountered so far, the value of the area will be stored as the new answer. To find the area of the largest rectangle of the histogram, use the â€˜LARGEST_RECTANGLEâ€™ function explained in our __The Largest Rectangular Area in Histogram__ blog. For a quick revision, the code to find the â€˜LARGEST_RECTANGLEâ€™ is given below.