Max rectangle-dynamic programming

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/