[C++] long but easy to understand. With description


#1

Take column-wise sum and store it in dp[i][j]. Then use thelargest rectangle in the histogram technique for each row of DP matrix.
for example matrix is [ [0 1 1] [1 1 1] [0 1 0] ]
dp matrix for this will be
[ [0 1 1]
[1 2 2]
[0 3 0]]
now see code you will get it.

/// function to compute max area in histogram refer ques "Largest Rectangle in Histogram"
int maxhistarea(vector<int> A){
    stack<int> st;
    int top=0, maxarea =0, i;
    for(i=0; i<A.size(); i++){
        while(!st.empty() && A[i]<A[st.top()]){
            int temp = st.top();
            st.pop();
            if(st.empty()) maxarea= max(maxarea, A[temp]*i);
            else 
                maxarea = max(maxarea, A[temp]*(i-st.top()-1));
        }
        st.push(i);
    }
    while(!st.empty()){
        int temp = st.top();
            st.pop();
            if(st.empty()) maxarea= max(maxarea, A[temp]*i);
            else 
                maxarea = max(maxarea, A[temp]*(i-st.top()-1));
    }
        return maxarea;
}
int Solution::maximalRectangle(vector<vector<int> > &A) {
    vector<vector<int>> dp(A.size(), vector<int> (A[0].size(), 0));
    for(int j=0; j<A[0].size(); j++){
        int count =0;
        for(int i=0; i<A.size(); i++){
            if(A[i][j] == 1) count++;
            else count =0;
            dp[i][j] = count; //compute column wise sum for 1.
        }
    }
    int ans = INT_MIN;
    for(int i=0; i<A.size(); i++){
            ans = max(ans, maxhistarea(dp[i]));
    }
    return ans;
}