85. Maximal Rectangle

Let left[j] be the left bottom point of the valid rectangle for point j. It'll be initialized by 0s and it is scanned from left to right. The state transition is shown as following:
If matrix[i][j] == '1', then left[j] = max(left[j], cur_l), else left[j] = 0 and cur_l = j+1.

Let right[j] be the right bottom point of the valid rectangle for point j. It'll be initialized by row's length and it is scanned from right to left. The state transition is shown as following:
If matrix[i][j] == '1', then right[j] = min(right[j], cur_r), else right[j] = cols and cur_r = j.

Let height[j] be the height of the valid rectangle for point j.
If matrix[i][j] == '1', then height[j]++, else height[j] = 0.

From the state transition above, the area is computed by (right[j] - left[j])*height[j].
So maxArea = max(maxArea, (right[j]-left[j])*height[j]).

1:  class Solution {  
2:  public:  
3:    int maximalRectangle(vector<vector<char>>& matrix) {  
4:      int rows = matrix.size();  
5:      if (rows == 0) return 0;  
6:      int cols = matrix[0].size();  
7:      vector<int> left(cols, 0), right(cols, cols), height(cols, 0);  
8:      int maxArea = 0;  
9:      for (int i = 0; i < rows; i++) {  
10:        int cur_l = 0, cur_r = cols;  
11:        for (int j = 0; j < cols; j++) {  
12:          if (matrix[i][j] == '1') {  
13:            height[j]++;  
14:          } else {  
15:            height[j] = 0;  
16:          }  
17:        }  
18:        for (int j = 0; j < cols; j++) {  
19:          if (matrix[i][j] == '1') {  
20:            left[j] = max(left[j], cur_l);  
21:          } else {  
22:            left[j] = 0;  
23:            cur_l = j+1;  
24:          }  
25:        }  
26:        for (int j = cols-1; j >= 0; j--) {  
27:          if (matrix[i][j] == '1') {  
28:            right[j] = min(right[j], cur_r);  
29:          } else {  
30:            right[j] = cols;  
31:            cur_r = j;  
32:          }  
33:        }  
34:        for (int j = 0; j < cols; j++) {  
35:          maxArea = max(maxArea, (right[j]-left[j])*height[j]);  
36:        }  
37:      }  
38:      return maxArea;  
39:    }  
40:  };