// Author : TangHanYi

// E-mail : thydeyx@163.com

// Create Date : 16-11-02 15:57:44

// File Name : Maximal_Rectangle.cpp

// Desc :

#include<iostream>

using namespace std;

class Solution {

public:

int maximalRectangle(vector<vector<char> > &matrix) {

if(matrix.empty()) return 0;

const int m = matrix.size();

const int n = matrix[0].size();

int left[n], right[n], height[n];

fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);

int maxA = 0;

for(int i=0; i<m; i++) {

int cur_left=0, cur_right=n;

for(int j=0; j<n; j++) { // compute height (can do this from either side)

if(matrix[i][j]=='1') height[j]++;

else height[j]=0;

}

for(int j=0; j<n; j++) { // compute left (from left to right)

if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);

else {left[j]=0; cur_left=j+1;}

}

// compute right (from right to left)

for(int j=n-1; j>=0; j--) {

if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);

else {right[j]=n; cur_right=j;}

}

// compute the area of rectangle (can do this from either side)

for(int j=0; j<n; j++)

maxA = max(maxA,(right[j]-left[j])*height[j]);

}

return maxA;

}

};

int main()

{

return 0;

}