AC Python DP solutioin 120ms based on largest rectangle in histogram
def maximalRectangle(self, matrix):\n        if not matrix or not matrix[0]:\n            return 0\n        n = len(matrix[0])\n        height = [0] * (n + 1)\n
    def maximalRectangle(self, matrix):\n        if not matrix or not matrix[0]:\n            return 0\n        n = len(matrix[0])\n        height = [0] * (n + 1)\n        ans = 0\n        for row in matrix:\n            for i in xrange(n):\n                height[i] = height[i] + 1 if row[i] == '1' else 0\n            stack = [-1]\n            for i in xrange(n + 1):\n                while height[i] < height[stack[-1]]:\n                    h = height[stack.pop()]\n                    w = i - 1 - stack[-1]\n                    ans = max(ans, h * w)\n                stack.append(i)\n        return ans\n\n    # 65 / 65 test cases passed.\n    # Status: Accepted\n    # Runtime: 120 ms\n    # 100%\n\nThe solution is based on [largest rectangle in histogram][1] solution. Every row in the matrix is viewed as the ground with some buildings on it. The building height is the count of consecutive 1s from that row to above rows. The rest is then the same as [this solution for largest rectangle in histogram][2]\n\n\n  [1]: https://leetcode.com/problems/largest-rectangle-in-histogram/\n  [2]: https://leetcode.com/discuss/65647/ac-python-clean-solution-using-stack-76ms
['Dynamic Programming', 'Python']