85

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int cLen, rLen, ans, i, j, p;
        rLen = matrix.size();
        if(!rLen) return 0;
        cLen = matrix[0].size();
        ans = 0;

        int leftMin[cLen], rightMin[cLen], height[cLen];
        memset(height, 0, sizeof(height));
        for(i=0; i<rLen; i++){
            for(j=0; j<cLen; j++){
                if(matrix[i][j] == '1') height[j]++;
                else height[j] = 0;
                leftMin[j] = rightMin[j] = 0;
            }

            leftMin[0] = -1;
            for(j=1; j<cLen; j++){
                p = j-1;
                while(p >= 0 && height[p] >= height[j])
                    p = leftMin[p];
                leftMin[j] = p;
            }

            rightMin[cLen-1] = cLen;
            for(j=cLen-2; j>=0; j--){
                p = j+1;
                while(p < cLen && height[p] >= height[j])
                    p = rightMin[p];
                rightMin[j] = p;
            }

            for(j=0; j<cLen; j++)
                ans = max(ans, height[j]*(rightMin[j]-leftMin[j]-1));
        }
        return ans;
    }
};