Histogram approach O(n^2) code likhne me phat gyi bhai :-)


#1
int Solution::maximalRectangle(vector<vector<int> > &A) {

int dp[A.size()][A[0].size()];

for(int i=0;i<A.size();i++)
{
    for(int j=0;j<A[0].size();j++)
    {
        if(i==0)
        {
            dp[i][j]=A[i][j];
        }
        
        else
        {
            if(A[i][j]==0)
            dp[i][j]=0;
            else
            {
                dp[i][j]=1+dp[i-1][j];
            }
        }
    }
}

int ans=INT_MIN;

for(int i=0;i<A.size();i++)
{

vector<int>lb;
    
    lb.push_back(-1);
    
    stack<int>s;
    s.push(0);
    for(int j=1;j<A[0].size();j++)
    {
        while(s.size()!=0)
        {
            if(dp[i][j]<=dp[i][s.top()])
                s.pop();
            
            else
            {
                lb.push_back(s.top());
                s.push(j);
                
                break;
            }
        }
        
        if(s.size()==0){
            lb.push_back(-1);
            s.push(j);
        }
    }
    
    while(s.size()!=0)
        s.pop();
    
    vector<int>rb;
    
    rb.push_back(A[0].size());
    
    
    s.push(A[0].size()-1);
    for(int j=A[0].size()-2;j>=0;j--)
    {
        while(s.size()!=0)
        {
            if(dp[i][j]<=dp[i][s.top()])
                s.pop();
            
            else
            {
                rb.push_back(s.top());
                s.push(j);
                
                break;
            }
        }
        
        if(s.size()==0){
            rb.push_back(A[0].size());
            s.push(j);
        }
    }
    reverse(rb.begin(),rb.end());
    
    
    for(int j=0;j<lb.size();j++)
    {
        ans =max(ans,dp[i][j]*(rb[j]-lb[j]-1));
    }
    
}    
    
    return ans;

}