C++ | DP | STACK | O(n) | Faster than 90%
\nclass Solution {\npublic:\n    int getarea(vector<vector<int>>&dp , int row , int n)\n    {\n        \n        vector<int> pre(n) ; \n        pre[0] = -1 ;\n 
```\nclass Solution {\npublic:\n    int getarea(vector<vector<int>>&dp , int row , int n)\n    {\n        \n        vector<int> pre(n) ; \n        pre[0] = -1 ;\n        vector<int> next(n) ;\n        next[n-1] = n ; \n        stack<int> s ; \n        s.push(0) ; \n        \n        for(int i = 1 ; i<n ; i++)\n        {\n            if(dp[row][s.top()] < dp[row][i]) \n            {\n                pre[i] = s.top() ; \n                s.push(i) ; \n            }\n            else\n            {\n                while(!s.empty() && dp[row][s.top()] >= dp[row][i]) \n                {\n                    s.pop() ; \n                }\n                if(s.empty())\n                {\n                    pre[i] = -1 ; \n                    s.push(i) ;\n                }\n                else\n                {\n                    pre[i] = s.top() ; \n                    s.push(i) ; \n                }\n            }\n        }\n        // s.clear() ; \n        while(!s.empty()) s.pop() ; \n        \n        s.push(n-1) ; \n        for(int i = n-2 ; i>=0 ; i--)\n        {\n            if(dp[row][s.top()] < dp[row][i]) \n            {\n                next[i] = s.top() ; \n                s.push(i) ; \n            }\n            else\n            {\n                while(!s.empty() && dp[row][s.top()] >= dp[row][i]) \n                {\n                    s.pop() ; \n                }\n                if(s.empty())\n                {\n                    s.push(i) ;\n                    next[i] = n ; \n                }\n                else\n                {\n                    next[i] = s.top() ; \n                    s.push(i) ; \n                }\n            }\n        }\n        int ans = INT_MIN ; \n        int area ; \n        for(int i = 0 ; i<n ; i++)\n        {\n            area = ( next[i] - pre[i] - 1) * dp[row][i] ; \n            ans = max(ans , area) ; \n        }\n        return ans ; \n    }\n    int maximalRectangle(vector<vector<char>>& matrix) {\n        \n        int n = matrix.size() ; \n        int m = matrix[0].size() ; \n        vector<vector<int>> dp(n , vector<int> (m)) ; \n        for(int i = 0 ; i<n ; i++)\n        {\n            for(int j = 0 ; j < m ; j++)\n            {\n                if(i == 0)\n                {\n                    if(matrix[i][j] == \'0\') dp[i][j] = 0 ;\n                    else dp[i][j] = 1 ; \n                    continue ;  \n                }\n                if(matrix[i][j] == \'0\') dp[i][j] = 0 ; \n                else dp[i][j] = dp[i-1][j] + 1 ; \n            }\n        }\n        int ans = INT_MIN ; \n        \n        for(int i = 0 ; i < n ; i++)\n        {\n            int area = getarea(dp , i , m ) ; \n            ans = max(ans , area) ;\n        }\n        return ans ; \n    }\n};\n```
['Dynamic Programming', 'Stack']