363.md

363. Max Sum of Rectangle No Larger Than K

Solution 1 (time O(n^2mlog(m)), space O(m))

class Solution(object):
    def maxSumSubmatrix(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        n, m = len(matrix), len(matrix[0])
        ans = -float("inf")
        for i in range(n):
            arr = [0] * m
            for j in range(i, n):
                pre_sum = [0]
                cur_sum = 0
                for p in range(m):
                    arr[p] += matrix[j][p]
                    cur_sum += arr[p]
                    idx = bisect.bisect_left(pre_sum, cur_sum - k)
                    if idx < len(pre_sum):
                        ans = max(ans, cur_sum - pre_sum[idx])
                    bisect.insort(pre_sum, cur_sum)
        return ans