Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger thank.
It is guaranteed that there will be a rectangle with a sum no larger than k.
Example 1:
**Input:** matrix = [[1,0,1],[0,-2,3]], k = 2
**Output:** 2
**Explanation:** Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).
Example 2:
**Input:** matrix = [[2,2,-1]], k = 3
**Output:** 3
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-100 <= matrix[i][j] <= 100
-105 <= k <= 105
Follow up: What if the number of rows is much larger than the number of columns?
ac
class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
// edge cases
int row = matrix.length, col = matrix[0].length;
int res = Integer.MIN_VALUE;
// 1) 2 pointers, iterate each col -> get sum array;
for (int l = 0; l < col; l++) {
int[] nums = new int[row];
for (int r = l; r < col; r++) {
for (int i = 0; i < row; i++) nums[i] += matrix[i][r];
// 3) can use Kadane's algorithm to early stop
int currMax = Integer.MIN_VALUE, globalMax = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
currMax = Math.max(currMax + nums[i], nums[i]);
globalMax = Math.max(globalMax, currMax);
}
if (globalMax <= k) {
res = Math.max(res, globalMax);
} else {
// 2) perform maxSum <= k calculation. TreeSet to help binary search find ceiling(currSum - k)
TreeSet<Integer> tset = new TreeSet<>();
tset.add(0);
int currSum = 0;
for (int n : nums) {
currSum += n;
// find currSum - oldSum <= k, so it's the ceiling of currSum - k
Integer oldSum = tset.ceiling(currSum - k);
if (oldSum != null) res = Math.max(res, currSum - oldSum);
tset.add(currSum);
}
}
if (res == k) return k; // earlier return
}
}
return res;
}
}
/*
convert to 1D array maxSum. 1) 2 pointers, iterate each col -> get sum array; 2) perform maxSum <= k calculation. TreeSet to help binary search find ceiling(currSum - k) 3) can use Kadane's algorithm to early stop
*/
