O(N^2) solution


#1
int maxRect(const vector<int>& A){
    int m=A.size();
    vector<int> sh{0};
    vector<int> sj{-1};
    int maxarea = 0;
    for(int j=0; j<=m; ++j){
	int h=(j==m?0:A[j]);
	if(h>sh.back()){
	    sh.push_back(h);
	    sj.push_back(j);
	} else while (h<sh.back()){
	    maxarea = max(maxarea, (j-sj.back())*sh.back());
	    if(sh[sh.size()-2]<h){
	        sh.back() = h;
	    } else {            
	        sh.pop_back();
	        sj.pop_back();
	    }
	    
	}
    }
    return maxarea;
}

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