0

Maximum size rectangle sub-matrix with all 1's

Difficulty: EASY
Avg. time to solve
10 min
Success Rate
80%

Problem Statement
Suggest Edit

You are given an N*M size binary-valued matrix, where N is the number of rows and M is the number of columns. You need to return the size (area) of maximum size submatrix which consists of all 1’s i.e. the maximum area of a submatrix in which each cell has only the value ‘1’.

subMatrix_image

In the above image, areas in green, red and violet colour are all submatrices of the original 4x4 matrix.

Note:

1. Binary valued matrix has only two values in each cell : 0 and 1.
2. A submatrix is a matrix formed by selecting certain rows and columns from a larger matrix.
3. The area of a matrix with h rows and w columns is equal to h*w. 
Input Format:
The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains two space-separated integers N and M, where N = number of rows in the given matrix and M = number of columns in the given matrix.

Then N lines follow for each test case:
Each line contains M space-separated integers(either 1 or 0).
Output Format:
Print the area of maximum size submatrix of all 1’s in the given matrix.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N,M <= 100

Time Limit: 1 sec
Sample Input 1:
1
5 4
1 0 1 1
1 0 1 1
0 1 0 1
1 1 1 1
0 0 0 1
Sample Output 1:
5
Explanation for Sample Input 1:

explanationSampleInput1

Sample Input 2:
1
4 4
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
Sample Output 2:
8
Want to solve this problem? Login now to get access to solve the problems