from sortedcontainers import SortedList
class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        ans = float("-inf")
        m, n = len(matrix), len(matrix[0])

        for i in range(m):   # 枚举上边界
            total = [0] * n
            for j in range(i, m):   # 枚举下边界
                for c in range(n):
                    total[c] += matrix[j][c]   # 更新每列的元素和
                
                totalSet = SortedList([0])
                s = 0
                for v in total:
                    s += v
                    lb = totalSet.bisect_left(s - k)
                    if lb != len(totalSet):
                        ans = max(ans, s - totalSet[lb])
                    totalSet.add(s)
        return ans

队列 二分查找 困难 每日一题 👆利用二分查找和前缀和的写法

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

👇python利用暴力搜索的方法会超时

class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])
        cum = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                cum[i][j] = cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1] + matrix[i-1][j-1]
        ans = -float('inf')
        for x1 in range(1,m+1):
            for y1 in range(1,n+1):
                for x2 in range(x1,m+1):
                    for y2 in range(y1,n+1):
                        cur = cum[x2][y2] - cum[x1-1][y2] - cum[x2][y1-1] + cum[x1-1][y1-1]
                        if cur <= k:
                            ans = max(cur,ans)
        return ans