Leetcode
Dynamic Programming
363 Max Sum of Rectangle No Larger Than K

1. Question

Given a non-empty 2D matrixmatrixand an integerk, find the max sum of a rectangle in thematrixsuch that its sum is no larger thank.
Example:
1
Given matrix = [
2
[1, 0, 1],
3
[0, -2, 3]
4
]
5
k = 2
Copied!
The answer is2. 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. 1.
    The rectangle inside the matrix must have an area > 0.
  2. 2.
    What if the number of rows is much larger than the number of columns?

2. Implementation

(1) DP + Binary Search
思路:
(1) 找出所有可能submatrix,这里利用一个技巧是建立一个rowSum数组,存储每个submatrix的row的和。我们利用两个for loop从左到右先固定每个submatrix的两列,然后在从上到下扫行,得到submatrix的sum
(2) 对每个rowSum, 其作用就类似于1维数组中的prefixSum,由于题目要找出submatrix 的sum要小于等于k的,而位于行i和j之间的submatrix的sum就等于rowSum[j] - rowSum[i - 1]。 也即我们要找到一个rowSum, 它的值是小于等于 rowSum[j] - k的。这可以利用二分法找这个rowSum的右边界。这里我们利用treeSet这个数据结构,方便我们找到这个值。这个做法和Minimum Subarray那道题利用prefixSum数组的二分法的思想相同
(3) 如果找到这个rowSum, 则我们可以得到submatrix的sum,然后以此找到小于等于K的最大的submatrix和
1
class Solution {
2
public int maxSumSubmatrix(int[][] matrix, int k) {
3
if (matrix == null || matrix.length == 0) {
4
return 0;
5
}
6
7
int m = matrix.length, n = matrix[0].length;
8
int res = Integer.MIN_VALUE;
9
10
for (int leftCol = 0; leftCol < n; leftCol++) {
11
int[] rowSum = new int[m];
12
13
for (int rightCol = leftCol; rightCol < n; rightCol++) {
14
15
for (int i = 0; i < m; i++) {
16
rowSum[i] += matrix[i][rightCol];
17
}
18
19
TreeSet<Integer> set = new TreeSet<>();
20
set.add(0);
21
int prefixSum = 0;
22
23
for (int sum : rowSum) {
24
prefixSum += sum;
25
Integer num = set.ceiling(prefixSum - k);
26
if (num != null) {
27
res = Math.max(res, prefixSum - num);
28
}
29
set.add(prefixSum);
30
}
31
}
32
}
33
return res;
34
}
35
}
Copied!
(2) Kadane Algorithm优化
思想: 这里的优化用Maximum Subarray里的kadane algorithm, 在我们遍历每个submatrix的的同时,我们利用maximum subarray的思路找出当前submatrix的最大值,如果该最大值小于等于K,则我们直接与res比较,而不必要通过treeSet,找到符合条件的submatrix sum
1
class Solution {
2
public int maxSumSubmatrix(int[][] matrix, int k) {
3
if (matrix == null || matrix.length == 0) {
4
return 0;
5
}
6
7
int m = matrix.length, n = matrix[0].length;
8
int res = Integer.MIN_VALUE;
9
10
for (int leftCol = 0; leftCol < n; leftCol++) {
11
int[] rowSum = new int[m];
12
13
for (int rightCol = leftCol; rightCol < n; rightCol++) {
14
int maxSum = Integer.MIN_VALUE;
15
int curMaxSum = 0;
16
17
for (int i = 0; i < m; i++) {
18
// Optimization with Kadane Algorithm
19
rowSum[i] += matrix[i][rightCol];
20
curMaxSum = Math.max(rowSum[i], curMaxSum + rowSum[i]);
21
maxSum = Math.max(maxSum, curMaxSum);
22
}
23
24
if (maxSum <= k) {
25
res = Math.max(maxSum, res);
26
continue;
27
}
28
29
TreeSet<Integer> set = new TreeSet<>();
30
set.add(0);
31
int prefixSum = 0;
32
33
for (int sum : rowSum) {
34
prefixSum += sum;
35
Integer num = set.ceiling(prefixSum - k);
36
if (num != null) {
37
res = Math.max(res, prefixSum - num);
38
}
39
set.add(prefixSum);
40
}
41
}
42
}
43
return res;
44
}
45
}
Copied!

3. Time & Space Complexity

DP + Binary Search: 时间复杂度O(mlogm * n^2), 空间复杂度O(m)
Kadane Algorithm优化: 时间复杂度O(mlogm * n^2), 空间复杂度O(m)