C++ Solution in O(N*M) time


#1
int MaxAreaOfHist(vector<int> &arr){
    stack<int> S;
    int n = arr.size(), i = 0, maxarea = 0;
    while(i < n){
        if(S.empty() || arr[i] >= arr[S.top()]){
            S.push(i); i++;
        }
        else{
            int tp = S.top();
            S.pop();
            if(S.empty())
                maxarea = max(maxarea, arr[tp]*i);
            else
                maxarea = max(maxarea, arr[tp]*(i-1-S.top()));
        }
    }
    while(!S.empty()){
        int tp = S.top();
        S.pop();
        if(S.empty())
            maxarea = max(maxarea, arr[tp]*i);
        else
            maxarea = max(maxarea, arr[tp]*(i-1-S.top()));
    }
    return maxarea;
}

int Solution::maximalRectangle(vector<vector<int> > &A) {
    int maxarea = MaxAreaOfHist(A[0]);
    for(int i=1; i<A.size(); i++){
        for(int j=0; j<A[i].size(); j++){
            if(A[i][j] != 0)
                A[i][j] += A[i-1][j];
        }
        maxarea = max(maxarea, MaxAreaOfHist(A[i]));
    }
    return maxarea;
}