/**
 * This problem can be simply converted to "Largest Rectangle in Histogram" problem,
 *     for each rows, calcuate the height in each columns than solve it.
 *
 * Since we could solve "Largest Rectangle in Histogram" in O(n), the run time for this
 *     question is just O(m) * (O(n) + O(n)), in which m is total rows and, first m is 
 *     for calculating heights, and second n is for cacualte reactangle area. In total
 *     it's O(mn);
 */


#include <vector>
#include <iostream>
#include <stack>

using namespace std;


int largestRectangleArea(vector<int> &height) {
    int size = height.size();

    vector<int> width(size);
    stack<int> limit;
    
    // find left-most reachable bar
    for (int i = 0; i < size; ++i) {
        int left = 0;
        while (!limit.empty()) {
            if (height[limit.top()] < height[i]) {
                left = limit.top()+1;
                break;
            } else {
                limit.pop();
            }
        }

        width[i] = left;
        limit.push(i);
    }

    limit = stack<int>();
    for (int i = size-1; i >= 0; --i) {
        int right = size-1;
        while(!limit.empty()) {
            if (height[limit.top()] < height[i]) {
                right = limit.top()-1;
                break;
            } else {
                limit.pop();
            }
        }

        width[i] = right-width[i]+1;
        limit.push(i);
    }

    int maxArea = 0;
    for (int i = 0; i < size; ++i) {
        int area = height[i]*width[i];
        if (maxArea < area) {
            maxArea = area;
        }
    }

    return maxArea;
}

int maximalRectangle(vector<vector<char> > &matrix) {
    int rows = matrix.size();
    if (rows == 0) return 0;

    int cols = matrix[0].size();
    vector<int> heights(cols);
    int maxArea = 0;

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (matrix[i][j] == '0') {
                heights[j] = 0;
            } else {
                heights[j] +=1;
            }
        }

        int area = largestRectangleArea(heights);
        if (maxArea < area) {
            maxArea = area;
        }
    }

    return maxArea;
}