2023.11.26 Today's Challenge

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

Largest Submatrix With Rearrangements - LeetCode

TL이 나기 쉬운 문제

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        m, n, ans = len(matrix), len(matrix[0]), 0
        prev_row = [0] * n

        for row in range(m):
            curr_row = matrix[row][:]
            for col in range(n):
                if curr_row[col] != 0:
                    curr_row[col] += prev_row[col]
                
            sorted_row = sorted(curr_row, reverse=True)
            for i in range(n):
                ans = max(ans, sorted_row[i] * (i+1))
            
            prev_row = curr_row
            
        return ans