Evolve from brute force to optimal
This problem is similar to maximal square but much more difficult.\n1. brute force O(n^6), count each rectangle\n\n    int maximalRectangle(vector<vector<char>>
This problem is similar to [maximal square](https://discuss.leetcode.com/topic/55063/evolve-from-brute-force-to-dp) but much more difficult.\n1. brute force O(n^6), count each rectangle\n```\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        if(matrix.empty()) return 0;\n        int r = matrix.size(), c = matrix[0].size(), area = 0;\n        for(int i=0;i<r;i++)\n            for(int j=0;j<c;j++) { //each start point (i,j)\n                if(matrix[i][j]=='0') continue;\n                for(int p=i;p<r;p++)\n                    for(int q=j;q<c;q++) { // each end point (p,q)\n                        if(matrix[p][q]=='0') continue;\n                        bool ones = 1;\n                        for(int x=i;x<=p;x++) {   //check if the rectangle contains all 1s\n                            for(int y=j;y<=q;y++) \n                                if(matrix[x][y] == '0') {\n                                    ones = 0;\n                                    break;\n                                }\n                            if(!ones) break;\n                        }\n                        if(ones) area = max(area, (p-i+1)*(q-j+1));\n                    }\n            }\n        return area;\n    }\n```\n2. O(n^4), whether a rectangle contains all 1s can be determined incrementally from the previous rectangle\n```\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        if(matrix.empty()) return 0;\n        int r = matrix.size(), c = matrix[0].size(), area = 0;\n        for(int i=0;i<r;i++)\n            for(int j=0;j<c;j++) {\n                vector<vector<bool>> dp(r,vector<bool>(c));\n                for(int p=i;p<r;p++)\n                    for(int q=j;q<c;q++) {\n                        dp[p][q] = matrix[p][q]=='1';\n                        if(p>i) dp[p][q] = dp[p][q] & dp[p-1][q];\n                        if(q>j) dp[p][q] = dp[p][q] & dp[p][q-1];\n                        if(dp[p][q]) area=max(area,(p-i+1)*(q-j+1));\n                        else break;\n                    }\n            }\n        return area;\n    }\n```\n3. O(n^3), for a start/end point, we do not need to consider all end/start points, we only need to consider points that connect to the start/end point by all 1s. We use a 2d array to cache number of consecutive 1s to the left of each point. Then for a point, we can determine its maximal rectangles in linear time. [The idea is from @uniqueness ](https://discuss.leetcode.com/topic/1122/my-o-n-3-solution-for-your-reference).\n```\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        int r = matrix.size();\n        if (!r) return 0;\n        int c = matrix[0].size(), area = 0;\n        vector<vector<int>> ones(r,vector<int>(c));\n        for(int i=0;i<r;i++) \n            for(int j=0;j<c;j++) {\n                if(matrix[i][j]=='0') continue;\n                int w = ones[i][j] = (j?ones[i][j-1]:0) + 1;\n                for(int k=i; k>=0; k--) {\n                    w = min(ones[k][j],w);\n                    area = max(area,w*(i-k+1));\n                }\n            }\n        return area;\n    }\n```\n4. O(n^2) dp. The optimal solution does not check a rectangle by start/end point. Given a point (i, j), it computes the left boundary, right boundary of the maximal rectangle with height(i,j) incrementally in constant time. [The idea is from @morrischen2008](https://discuss.leetcode.com/topic/6650/share-my-dp-solution).\n```\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        int r = matrix.size();\n        if (!r) return 0;\n        int c = matrix[0].size(), area = 0;\n        vector<int> left(c), right(c,c), height(c);\n        for(int i=0;i<r;i++) { \n            int cur = 0;\n            for(int j=0;j<c;j++)\n                if(matrix[i][j]=='0') {\n                    height[j] = left[j] = 0;\n                    cur = j+1; //left boundary of current row\n                } else {\n                    left[j] = max(left[j],cur);  //left boundary for height[j]\n                    height[j]++;\n                }\n            cur = c;\n            for(int j=c-1;j>=0;j--) {\n                if (matrix[i][j]=='0') cur = j;\n                right[j] = matrix[i][j]=='0'? c:min(right[j],cur);\n                area = max(height[j]*(right[j]-left[j]),area);\n            }\n        }\n        return area;\n    }\n```
[]