LeetCode Solutions
363. Max Sum of Rectangle No Larger Than K
class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
const int m = matrix.size();
const int n = matrix[0].size();
int ans = INT_MIN;
for (int baseCol = 0; baseCol < n; ++baseCol) {
// sums[i] := sum(matrix[i][baseCol..j])
vector<int> sums(m, 0);
for (int j = baseCol; j < n; ++j) {
for (int i = 0; i < m; ++i)
sums[i] += matrix[i][j];
// Find the max subarray no more than k
set<int> accumulate{0};
int prefix = 0;
for (const int sum : sums) {
prefix += sum;
const auto it = accumulate.lower_bound(prefix - k);
if (it != cend(accumulate))
ans = max(ans, prefix - *it);
accumulate.insert(prefix);
}
}
}
return ans;
}
};
class Solution {
public int maxSumSubmatrix(int[][] matrix, int k) {
final int m = matrix.length;
final int n = matrix[0].length;
int ans = Integer.MIN_VALUE;
for (int baseCol = 0; baseCol < n; ++baseCol) {
// sums[i] := sum(matrix[i][baseCol..j])
int[] sums = new int[m];
for (int j = baseCol; j < n; ++j) {
for (int i = 0; i < m; ++i)
sums[i] += matrix[i][j];
// Find the max subarray no more than k
TreeSet<Integer> accumulate = new TreeSet<>(Arrays.asList(0));
int prefix = 0;
for (final int sum : sums) {
prefix += sum;
final Integer lo = accumulate.ceiling(prefix - k);
if (lo != null)
ans = Math.max(ans, prefix - lo);
accumulate.add(prefix);
}
}
}
return ans;
}
}