LC 1727. 重新排列后的最大子矩阵

https://leetcode-cn.com/problems/largest-submatrix-with-rearrangements/

这么简单的题目愣没有想出来，看了提示1 ”For each column, find the number of consecutive ones ending at each position.” 才有点思路。

这题正确的想法是，假设矩阵的ending row在i上的话，那么每个列的最大高度是多少，然后计算出所有可能矩阵的最大面积。

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        n, m = len(matrix), len(matrix[0])
        hs = [0] * m
        ans = 0
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == 1:
                    hs[j] += 1
                else:
                    hs[j] = 0

            tmp = hs.copy()
            tmp.sort(reverse=True)
            for j in range(m):
                area = (j + 1) * tmp[j]
                ans = max(ans, area)

        return ans