最大矩形

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param matrix int整型二维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/5720efc1bdff4ca3a7dad37ca012cb60?tpId=196&tqId=39479&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        1. 构建动态规划矩阵
            设dp[i][j]表示第i行以元素matrix[i][j]结尾的连续1的个数
            状态转移方程：
                若matrix[i][j] == 0:
                    dp[i][j] = 0
                否则：
                     dp[i][j] = 1 if j == 0 else dp[i][j - 1] + 1
        2. 遍历矩阵dp，对于dp[i][j]，我们从第i行枚举到0行，不断计算以matrix[i][j]为右下角的最大矩形面积，并更新res
    复杂度：
        时间复杂度：O(mn)
        空间复杂度：O(mn)
    """

    def maximalRectangle(self, matrix):
        # write code here
        m, n = len(matrix), len(matrix[0])

        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            if matrix[i][0] == 1:
                dp[i][0] = 1
        for i in range(m):
            for j in range(1, n):
                if matrix[i][j] == 1:
                    dp[i][j] = dp[i][j - 1] + 1
        # print dp

        res = 0
        for i in range(m):
            for j in range(n):
                if dp[i][j] == 0:
                    continue
                area, width = dp[i][j], dp[i][j]
                for k in range(i - 1, -1, -1):
                    width = min(width, dp[k][j])
                    area = max(area, width * (i - k + 1))
                res = max(res, area)
        return res


if __name__ == "__main__":
    sol = Solution()

    # matrix = [[1]]

    # matrix = [[1, 1], [0, 1]]

    # matrix = [[0, 0], [0, 0]]

    matrix = [[1, 0, 1, 0, 0], [1, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]]

    res = sol.maximalRectangle(matrix)

    print res