2026-01-11 13:52:04 +0300 MSK

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * (n + 1)  for _ in range(m + 1)]
        max_area = 0

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == "0":
                    continue
                dp_i, dp_j = i + 1, j + 1
                width = dp[dp_i][dp_j - 1] + 1
                dp[dp_i][dp_j] = width
                max_area = max(max_area, width)
                for cur_dp_i in reversed(range(1, dp_i)):
                    height = dp_i - cur_dp_i + 1
                    width = min(width, dp[cur_dp_i][dp_j])
                    if width == 0:
                        break
                    max_area = max(max_area, height * width)
        
        return max_area