Easiest to understand O(n2) c++ solution


#1
int findMaxRectangle(vector<int> A){
    int n = A.size();
    stack<int> s;
    int l[n]; int r[n];
    
    for(int i=0;i<n;i++){
        while(!s.empty() && A[s.top()] >= A[i]){
            s.pop();
        }
        if(s.empty()) l[i] = -1;
        else l[i] = s.top();
        s.push(i);
    }
    while(!s.empty()){
        s.pop();
    }
    
    for(int i=n-1;i>=0;i--){
        while(!s.empty() && A[s.top()] >= A[i]){
            s.pop();
        }
        if(s.empty()) r[i] = n;
        else r[i] = s.top();
        s.push(i);
    }
    int ret = 0;
    for(int i=0;i<n;i++){
        int cur = A[i]*(r[i]-l[i]-1);
        ret = max(cur,ret);
    }
    return ret;
}

int Solution::maximalRectangle(vector<vector<int> > &A) {
    int m = A.size();
    int n = A[0].size(),maxArea = 0;
    for(int i=1;i<m;i++)
    for(int j=0;j<n;j++){
        if(A[i][j]==1) A[i][j] += A[i-1][j];
    }
    for(int i=0;i<m;i++){
        int curArea = findMaxRectangle(A[i]);
        maxArea = max(curArea,maxArea);
    }
    return maxArea;
}

#2

I am glad that to see this solution, good use of the histogram logic.