Max Rectangle in Binary Matrix

• Time : $O(nm)$
• Space : $O(m)$

int helper(vector<int>& A) {
    int res = 0;
    vector<pair<int, int>> st;
    A.push_back(0);
    for(int i = 0; i < A.size(); i++) {
        int p = i;
        while(!st.empty() and st.back().first >= A[i]) {
            auto [h,pos] = st.back(); st.pop_back();
            res = max(res, h * (i - pos));
            p = pos;
        }
        if(A[i]) st.push_back({A[i],p});
    }
    A.pop_back();
    
    return res;
}

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