## 题目描述：

LeetCode 363. Max Sum of Rectangle No Larger Than 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:

```Given matrix = [
[1,  0, 1],
[0, -2, 3]
]
k = 2```

​The answer is `2`. 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?

## 题目大意：

1. 矩阵内部的矩形面积必须 > 0。
2. 如果矩阵的行数远大于列数时，算法应当怎样调整？

## 解题思路：

`sums[i] = Σ(matrix[i][x..y])`

## Java代码：

``````public class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
int m = matrix.length, n = 0;
if (m > 0) n = matrix[0].length;
if (m * n == 0) return 0;

int M = Math.max(m, n);
int N = Math.min(m, n);

int ans = Integer.MIN_VALUE;
for (int x = 0; x < N; x++) {
int sums[] = new int[M];
for (int y = x; y < N; y++) {
TreeSet<Integer> set = new TreeSet<Integer>();
int num = 0;
for (int z = 0; z < M; z++) {
sums[z] += m > n ? matrix[z][y] : matrix[y][z];
num += sums[z];
if (num <= k) ans = Math.max(ans, num);
Integer i = set.ceiling(num - k);
if (i != null) ans = Math.max(ans, num - i);
}
}
}
return ans;
}
}``````

``````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
``````

Pingbacks已关闭。