LC1727. Largest Submatrix With Rearrangements

class Solution:
    def largestSubmatrix(self, A: List[List[int]]) -> int:
        """tc O(R*ClgC) sc O(C)
        1. for each row, its colom's accumutive height 
        2. based on current height on one row, sort height, get optimal submatix area
        3. compare each row's max submatrix area, get the max 
        
        """
        r = len(A)
        c = len(A[0])
        hs = [0] * c 
        res = 0
        for i in range(r):
            for j in range(c):
                if A[i][j] == 1:
                    hs[j] += 1
                else:
                    hs[j] = 0
            res= max(res,self.get_max_S(hs[:]))
        return res 
    
    def get_max_S(self,H):
        n = len(H)
        H.sort()
        res = 0
        for i in range(n):
            h = H[i]
            res = max(res,h*(n-i))
        return res