Given a binary matrix. Find the maximum area of a rectangle formed only of 1s in the given matrix.

Your task is to complete the function maxArea which returns the maximum size rectangle area in a binary-sub-matrix with all 1’s. The function takes 3 arguments the first argument is the Matrix M[ ] [ ] and the next two are two integers n and m which denotes the size of the matrix M.

```Input:
n = 4, m = 4
M[][] = {{0 1 1 0},
{1 1 1 1},
{1 1 1 1},
{1 1 0 0}}
Output: 8
Explanation: For the above test case the
matrix will look like
0 1 1 0
1 1 1 1
1 1 1 1
1 1 0 0
the max size rectangle is
1 1 1 1
1 1 1 1
and area is 4 *2 = 8.```

lets use dynamic programming and area of histogram to solve this sum:
if you want to see area of histogram than check this link https://codemummy.blogspot.com/2020/08/maximum-area-of-histogram-stack.html

c++ implementation:

```// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000

int maxArea(int M[MAX][MAX], int n, int m);
int main() {
int T;
cin >> T;

int M[MAX][MAX];

while (T--) {
int n, m;
cin >> n >> m;

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> M[i][j];
}
}
cout << maxArea(M, n, m) << endl;
}
}
// } Driver Code Ends

//function required to find the max area of histogram:
long long maxareahist(int a[],int n)
{
long long area=0; int i=0; long long mxarea=0;
stack<int>s;

while(i<n)
{
if(s.empty() || a[s.top()] <=a[i])
s.push(i++);

else
{
int y= s.top();
s.pop();

if(s.empty())
area=a[y]*i;
else
area=a[y]*(i-s.top()-1);

mxarea=max(area,mxarea);
}
}

while(!s.empty())
{
int y= s.top();
s.pop();

if(s.empty())
area=a[y]*i;
else
area=a[y]*(i-s.top()-1);

mxarea=max(area,mxarea);

}
return mxarea;
}
//function to calculate the max area in matrix:
int maxArea(int M[MAX][MAX], int n, int m) {
int maxx=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{   if(i!=0)
{
if(M[i][j]!=0)
M[i][j]=M[i-1][j]+M[i][j];
else
M[i][j]=0;
}
}
}

for(int i=0;i<n;i++)
{
int k=maxareahist(M[i],m);
maxx=max(k,maxx);
}

return maxx;
}
```

we run a loop to traverse through the rows.
Now If the current row is not the first row then update the row as follows, if matrix[i][j] is not zero then matrix[i][j] = matrix[i-1][j] + matrix[i][j].
Find the maximum rectangular area under the histogram, consider the ith row as heights of bars of a histogram.

if you want to solve this question:
https://practice.geeksforgeeks.org/problems/max-rectangle/1/

darkmode