在C ++中，矩形的最大和不大于K
假设我们有一个2D矩阵和一个整数k。我们必须找到矩阵中矩形的最大和，以使其总和不大于k。所以，如果输入像-
且k=3，则输出将为3，因为标记矩形的总和为3。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数maxSumSubmatrix()，它将取一个2D数组矩阵和k，
n：=行号，m：=列号
ans：=-inf
对于初始化l：=0，当l<m时，更新（将l增加1），-
定义一个大小为n的数组rowSum
对于初始化r：=l，当r<m时，更新（将r增加1），-
currSum：=currSum+rowSum[i]
它：=集的第一个元素，不大于currSum–k
如果不等于s的最后一个元素，则-
将currSum插入s
ans：=ans和(currSum-it)的最大值
rowSum[i]：=rowSum[i]+矩阵[i，r]
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
定义一组
将0插入s
currSum：=0
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
返回ans
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
int m = matrix[0].size();
int ans = INT_MIN;
for(int l = 0; l < m; l++){
vector <int> rowSum(n);
for(int r = l; r < m; r++){
for(int i = 0; i < n; i++)rowSum[i] += matrix[i][r];
set < int > s;
s.insert(0);
int currSum = 0;
for(int i = 0; i < n; i++){
currSum += rowSum[i];
set <int> :: iterator it = s.lower_bound(currSum - k);
if(it != s.end()){
ans = max(ans, (currSum - *it));
}
s.insert(currSum);
}
}
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,0,1},{0,-3,2}};
cout << (ob.maxSumSubmatrix(v, 3));
}输入值
[{1,0,1},{0,-3,2}]
3输出结果
3