[LeetCode] 363. Max Sum of Rectangle No Larger Than K

 Problem : https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        if not matrix or not matrix[0]: return 0
        
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        result = -2 ** 31
        
        for left in range(COLUMN):
            rowSums = [0] * ROW
            
            for right in range(left, COLUMN):
                
                for i in range(ROW):
                    rowSums[i] += matrix[i][right]
                    
                # find the max subarry no more than k
                dp = [0]
                total = 0

                for rsum in rowSums:
                    total += rsum

                    i = bisect.bisect_left(dp, total - k)
                    if i < len(dp): 
                        result = max(result, total - dp[i])

                    bisect.insort(dp, total)
            
        return result