[Python3] DYNAMIC PROGRAMMING, Explained
First, we form an auxiliary matrix dp storing the number of consecutive "1"s on the left side of the corresponding slot at the input matrix. Then we iterate slo
First, we form an auxiliary matrix `dp` storing the number of consecutive "1"s on the left side of the corresponding slot at the input matrix. Then we iterate slots of the `dp` upwards and find all possible rectangles that can be formed having the current slot as the right bottom angle. The first possible rectangle area is equal to `dp[i][j] * 1`. We go up and check whether the above slot can form a rectangle with the current one and if yes, the rectangle area will be equal to `min(dp[i][j], dp[i - 1][j]) * 2`, and so on. The maximum value is our result.\n\nTime: **O(rows*cols * rows)**  - because when searching for a max rectangle using our `dp`, in worst case we have to scan all rows up to the first one for every slot\nSpace: **O(rows*cols)** - for an aux matrix\n\nRuntime: 420 ms, faster than **20.81%** of Python3 online submissions for Maximal Rectangle.\nMemory Usage: 15.6 MB, less than **21.06%** of Python3 online submissions for Maximal Rectangle.\n\n```\nclass Solution:\n    def maximalRectangle(self, m: List[List[str]]) -> int:\n        rows = len(m)\n        if not rows:\n            return 0\n        \n        cols = len(m[0])\n        \n        dp = [[0] * cols for _ in range(rows)]\n\n        for i in range(rows): # fill dp, value = number of 1s on the left side\n            acc = 0\n            \n            for j in range(cols):\n                if m[i][j] == "1":\n                    acc += 1\n                else:\n                    acc = 0\n                    \n                dp[i][j] = acc\n                \n        res = 0\n        \n        for i in reversed(range(rows)):\n            for j in reversed(range(cols)):\n                bSide, rSide = dp[i][j], 0 # bottom and right side\n                k = i\n                \n                while k > -1 and dp[k][j]:  # iterate all possible rectangles\n                    bSide = min(bSide, dp[k][j])\n                    rSide += 1\n\n                    res = max(res, bSide * rSide)\n                    \n                    k -= 1\n                \n        return res\n```
['Dynamic Programming']