A O(n^2) solution based on Largest Rectangle in Histogram
This question is similar as [\[Largest Rectangle in Histogram\]][1]:\n\nYou can maintain a row length of Integer array H recorded its height of '1's, and scan a
This question is similar as [\\[Largest Rectangle in Histogram\\]][1]:\n\nYou can maintain a row length of Integer array H recorded its height of '1's, and scan and update row by row to find out the largest rectangle of each row.\n\nFor each row, if matrix[row][i] == '1'. H[i] +=1, or reset the H[i] to zero.\nand accroding the algorithm of [Largest Rectangle in Histogram], to update the maximum area.\n\n    public class Solution {\n        public int maximalRectangle(char[][] matrix) {\n            if (matrix==null||matrix.length==0||matrix[0].length==0)\n                return 0;\n            int cLen = matrix[0].length;    // column length\n            int rLen = matrix.length;       // row length\n            // height array \n            int[] h = new int[cLen+1];\n            h[cLen]=0;\n            int max = 0;\n            \n            \n            for (int row=0;row<rLen;row++) {\n                Stack<Integer> s = new Stack<Integer>();\n                for (int i=0;i<cLen+1;i++) {\n                    if (i<cLen)\n                        if(matrix[row][i]=='1')\n                            h[i]+=1;\n                        else h[i]=0;\n                    \n                    if (s.isEmpty()||h[s.peek()]<=h[i])\n                        s.push(i);\n                    else {\n                        while(!s.isEmpty()&&h[i]<h[s.peek()]){\n                            int top = s.pop();\n                            int area = h[top]*(s.isEmpty()?i:(i-s.peek()-1));\n                            if (area>max)\n                                max = area;\n                        }\n                        s.push(i);\n                    }\n                }\n            }\n            return max;\n        }\n    }\n\n  [1]: http://oj.leetcode.com/problems/largest-rectangle-in-histogram/
[]