# 363. Max Sum of Rectangle No Larger Than K 矩形区域不超过 K 的最大数值和

## # 题目描述：

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Example:

``````Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2,
and 2 is the max number no larger than k (k = 2).
``````

Note:

1. The rectangle inside the matrix must have an area > 0.
2. What if the number of rows is much larger than the number of columns?

## # 解题方法

### # 方法一：暴力求解(TLE)

``````class Solution(object):
def maxSumSubmatrix(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
if not matrix or not matrix[0]: return 0
M, N = len(matrix), len(matrix[0])
sums = [[0] * N for _ in range(M)]
res = float("-inf")
for m in range(M):
for n in range(N):
t = matrix[m][n]
if m > 0:
t += sums[m - 1][n]
if n > 0:
t += sums[m][n - 1]
if m > 0 and n > 0:
t -= sums[m - 1][n - 1]
sums[m][n] = t
for r in range(m + 1):
for c in range(n + 1):
d = sums[m][n]
if r > 0:
d -= sums[r - 1][n]
if c > 0:
d -= sums[m][c - 1]
if r > 0 and c > 0:
d += sums[r - 1][c - 1]
if d <= k:
res = max(res, d)
return res
``````

### # 方法二：Kadane's algorithm (TLE)

``````class Solution(object):
def maxSumSubmatrix(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
if not matrix or not matrix[0]: return 0
L, R = 0, 0
curSum, maxSum = float('-inf'), float('-inf')
maxLeft, maxRight, maxUp, maxDown = 0, 0, 0, 0
M, N = len(matrix), len(matrix[0])
for L in range(N):
curArr = [0] * M
for R in range(L, N):
for m in range(M):
curArr[m] += matrix[m][R]
curSum = self.getSumArray(curArr, M, k)
if curSum > maxSum:
maxSum = curSum
return maxSum

def getSumArray(self, arr, M, k):
sums = [0] * (M + 1)
for i in range(M):
sums[i + 1] = arr[i] + sums[i]
res = float('-inf')
for i in range(M):
for j in range(i + 1, M + 1):
curSum = sums[j] - sums[i]
if curSum <= k and curSum > res:
res = curSum
return res
``````

### # 方法二：Kadane's algorithm + 二分查找 (Accepted)

``````class Solution(object):
def maxSumSubmatrix(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
m = len(matrix)
n = len(matrix[0]) if m else 0

M = max(m, n)
N = min(m, n)
ans = None
for x in range(N):
sums = [0] * M
for y in range(x, N):
slist, num = [], 0
for z in range(M):
sums[z] += matrix[z][y] if m > n else matrix[y][z]
num += sums[z]
if num <= k:
ans = max(ans, num)
i = bisect.bisect_left(slist, num - k)
if i != len(slist):
ans = max(ans, num - slist[i])
bisect.insort(slist, num)
return ans or 0
``````