We could handle it by rows.
In each row, it is easily to get the maximum height of the current column by DP. Because dp[i][j] = dp[i - 1][j] + 1 if matrix[i][j] is 1, else it is 0.
With this dp array, we could use the algorithm we used in problem <85. Largest Rectangle in Histogram> to get the maximum area of the rectangle ends with each node.
class Solution: def maximalRectangle(self, matrix: List[List[str]]) -> int: if not matrix or not matrix: return 0 m, n = len(matrix), len(matrix) dp =  * (n + 1) max_area = 0 for i in range(m): # Use DP to get the height of each column for j in range(n): if matrix[i][j] == "1": dp[j] += 1 else: dp[j] = 0 # Use stack to get the maximum area stack = [[-1, -1]] for index, height in enumerate(dp): i = index while stack[-1] >= height: h, i = stack.pop() area = h * (index - i) max_area = max(area, max_area) stack.append([height, i]) return max_area