363 Max Sum of Rectangle No Larger Than K

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.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?
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)

361 Bomb Enemy

368 Largest Divisible Subset

Last modified 2yr ago

Copy link

Contents

363. Max Sum of Rectangle No Larger Than K

1. Question

2. Implementation

3. Time & Space Complexity

363. Max Sum of Rectangle No Larger Than K​

1. Question

2. Implementation

3. Time & Space Complexity

363. Max Sum of Rectangle No Larger Than K