Problem 61: Maximum Sum Submatrix No Larger Than K
Problem Statement: Given an m x n matrix and an integer k, find the maximum sum of any non-empty submatrix such that the sum is no larger than k.
Input
The first line contains three integers m, n, and k. Each of the next m lines contains n space-separated integers.
Output
Print the maximum sum of any submatrix with sum <= k.
Examples
Input:
2 3 2
1 0 1
0 -2 3
Output:
2
Solution Explanation
For each pair of rows, collapse the 2D array into a 1D array and then use a balanced BST or prefix sum technique to find the best subarray sum no larger than k.
Solution in C++
#include
#include
#include
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n, k;
cin >> m >> n >> k;
vector> matrix(m, vector(n));
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++)
cin >> matrix[i][j];
}
int ans = -1000000000;
for(int top = 0; top < m; top++){
vector dp(n, 0);
for(int bottom = top; bottom < m; bottom++){
for(int j = 0; j < n; j++){
dp[j] += matrix[bottom][j];
}
set bst;
bst.insert(0);
int curSum = 0;
for(int val : dp){
curSum += val;
auto it = bst.lower_bound(curSum - k);
if(it != bst.end()){
ans = max(ans, curSum - *it);
}
bst.insert(curSum);
}
}
}
cout << ans << "\n";
return 0;
}