Share my DP solution
The DP solution proceeds row by row, starting from the first row. Let the maximal rectangle area at row i and column j be computed by [right(i,j) - left(i,j)]he
The DP solution proceeds row by row, starting from the first row. Let the maximal rectangle area at row i and column j be computed by [right(i,j) - left(i,j)]*height(i,j).\n\nAll the 3 variables left, right, and height can be determined by the information from previous row, and also information from the current row. So it can be regarded as a DP solution. The transition equations are:\n\n> left(i,j) = max(left(i-1,j), cur_left), cur_left can be determined from the current row\n\n> right(i,j) = min(right(i-1,j), cur_right), cur_right can be determined from the current row \n\n> height(i,j) = height(i-1,j) + 1,  if matrix[i][j]=='1'; \n\n> height(i,j) = 0,  if matrix[i][j]=='0'\n\n\n\nThe code is as below. The loops can be combined for speed but I separate them for more clarity of the algorithm.\n\n    class Solution {public:\n    int maximalRectangle(vector<vector<char> > &matrix) {\n        if(matrix.empty()) return 0;\n        const int m = matrix.size();\n        const int n = matrix[0].size();\n        int left[n], right[n], height[n];\n        fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);\n        int maxA = 0;\n        for(int i=0; i<m; i++) {\n            int cur_left=0, cur_right=n; \n            for(int j=0; j<n; j++) { // compute height (can do this from either side)\n                if(matrix[i][j]=='1') height[j]++; \n                else height[j]=0;\n            }\n            for(int j=0; j<n; j++) { // compute left (from left to right)\n                if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);\n                else {left[j]=0; cur_left=j+1;}\n            }\n            // compute right (from right to left)\n            for(int j=n-1; j>=0; j--) {\n                if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);\n                else {right[j]=n; cur_right=j;}    \n            }\n            // compute the area of rectangle (can do this from either side)\n            for(int j=0; j<n; j++)\n                maxA = max(maxA,(right[j]-left[j])*height[j]);\n        }\n        return maxA;\n    }\n};\n\n\nIf you think this algorithm is not easy to understand, you can try this example:\n\n    0 0 0 1 0 0 0 \n    0 0 1 1 1 0 0 \n    0 1 1 1 1 1 0\n\nThe vector "left" and "right" from row 0 to row 2 are as follows\n\nrow 0:\n \n\n    l: 0 0 0 3 0 0 0\n    r: 7 7 7 4 7 7 7\n\nrow 1:\n\n    l: 0 0 2 3 2 0 0\n    r: 7 7 5 4 5 7 7 \n\nrow 2:\n\n    l: 0 1 2 3 2 1 0\n    r: 7 6 5 4 5 6 7\n\nThe vector "left" is computing the left boundary. Take (i,j)=(1,3) for example. On current row 1, the left boundary is at j=2. However, because matrix[1][3] is 1, you need to consider the left boundary on previous row as well, which is 3. So the real left boundary at (1,3) is 3. \n\nI hope this additional explanation makes things clearer.
[]