Leecode #363 矩形区域不超过K的最大数值和

给定一个非空二维矩阵 matrix 和一个整数 k，找到这个矩阵内部不大于 k 的最大矩形和。

示例

输入: matrix = [[1,0,1],[0,-2,3]], k = 2
输出: 2 
解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

说明：

1. 矩阵内的矩形区域面积必须大于 0。
2. 如果行数远大于列数，你将如何解答呢？

解题思路

先说一个公认的思路，确定这个区域是从第i列到第j列，然后我们就可以寻找这个区域是从第几行到第几行。把这个二维的问题转换为一维的问题，即求一列数组中不大于k的最大连续子序列和，对于这个问题又有多种解法，关键思想就是前缀和

1. 二分寻找 + 排序

def maxSumSubmatrix(self, matrix, k):
    row = len(matrix)
    col = len(matrix[0])
    rlt = float('-inf')
    for i in range(col):
      for j in range(i, col):
        arr = [0]
        temp = 0
        for m in range(row):
          temp += sum(matrix[m][i:j+1])
          loc = bisect.bisect_left(arr, temp - k)
          if loc < len(arr): rlt = max(rlt, temp - arr[loc])
          arr.append(temp)
          arr = sorted(arr)
    return rlt

令arr[i]表示数组第0位到i位的和，我们的目标函数f(i, j) = arr[i] - arr[j] <= k (i>j)，即arr[i] -k <= arr[j]，因此我们每次只要往前寻找arr[j]满足大于且最接近arr[i]-k，这里用到bisect模块来寻找，需要注意的一点是每次往数组中加入新元素后都要重新排序（可以用二分插入排序提高效率）

执行用时 3152ms，内存消耗14.9

2. 进一步优化

上一步中每次一列的和都要重新求，其实浪费了很多计算资源，另外数组插入后重新排序也浪费了许多时间

def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        import bisect
        row = len(matrix)
        col = len(matrix[0])
        res = float("-inf")
        for left in range(col):
            _sum = [0] * row
            for right in range(left, col):
                for j in range(row):
                    _sum[j] += matrix[j][right]
                arr = [0]
                cur = 0
                for tmp in _sum:
                    cur += tmp
                    loc = bisect.bisect_left(arr, cur - k)
                    if loc < len(arr):res = max(cur - arr[loc], res)
                    bisect.insort(arr, cur)
        return res

执行时间 1224ms 消耗空间 14.6ms

3. Kadane Algorithm

看到一个大佬的算法，目前速度最快

使用kadane算法直接求子序列的最大和，若大于k，就用暴力求解小于k的最大子序列和

def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        max_k = float("-inf")
        for l in range(len(matrix[0])):
            dp = [0] * len(matrix)
            for r in range(l, len(matrix[0])):
                for i in range(len(matrix)):
                    dp[i] += matrix[i][r]
                sum_dp = 0
                max_dp = float("-inf")
                for d in dp:
                    if sum_dp > 0:
                        sum_dp += d
                    else:
                        sum_dp = d
                    if sum_dp > max_dp:
                        max_dp = sum_dp
                if max_dp <= k:
                    max_k = max(max_k, max_dp)
                    continue
                for t in range(len(dp)):
                    sum_dp = 0
                    for b in range(t, len(dp)):
                        sum_dp += dp[b]
                        if max_k < sum_dp <= k:
                            max_k = sum_dp
                            if max_k == k:
                                return k

        return max_k