# C++ Divide & Conquer 32ms

• ``````class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if(matrix.empty()) return 0;
int m = matrix.size();
int n = matrix[0].size();
int res = 0;
vector<int> height(n,0);

for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
int val = matrix[i][j] - '0';
if(val == 0){height[j] = 0;}
else{height[j] = height[j] + val;}
}
int area = maxArea(height, 0, n-1);
res = max(res, area);
}
return res;
}

int maxArea(vector<int>& height, int s, int e){
if(s == e) return height[s];
int m = s + (e - s)/2;
int max_area = maxArea(height, s, m);
max_area = max(maxArea(height, m+1, e), max_area);
max_area = max(maxCombinArea(height, s, m, e), max_area);
return max_area;
}

int maxCombinArea(vector<int>& height, int s, int m, int e){
int i = m, j = m+1;
int max_area = 0, h = min(height[i], height[j]);
while( i >= s && j <= e){
h = min(h, min(height[i],height[j]));
max_area = max(max_area, h*(j - i + 1));
if(i == s){++j;}
else if (j == e){--i;}
else{
if(height[i-1] > height[j+1]){--i;}
else{++j;}
}
}
return max_area;
}     };``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.