Simple and Clean C++ solution

interview-questions
Tags: #<Tag:0x00007f2428250d98>

#1

Comment body goes here.

int MAH(vector<int>& arr, int n) {
stack<int> st;
int maxA = 0;
int i = 0;
while(i < n) {
    if(st.empty() || arr[i] >= arr[st.top()])
        st.push(i++);
    else {
        int index = st.top();
        st.pop();
        
        int area;
        if(st.empty())
            area = arr[index]*i;
        else
            area = arr[index] * ( i - st.top() - 1);
        maxA = max(maxA, area);
    }
}

while(!st.empty()) {
    int index = st.top();
    st.pop();
    
    int area;
    if(st.empty())
        area = arr[index]*i;
    else
        area = arr[index] * ( i - st.top() - 1);
    maxA = max(maxA, area);
}
return maxA;
}

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

int maxA = 0;
int row = A.size();
int col = A[0].size();

for(int i = 1; i<row; i++) {
    for(int j = 0; j<col; j++) {
        if(A[i][j] == 1)
            A[i][j] += A[i-1][j];
    }
}

for(vector<int> vec: A) {
    maxA = max(maxA, MAH(vec, col));
}

return maxA;

}