C++ 中求不大于 k 的矩形的最大和
c++server side programmingprogramming
假设我们有一个二维矩阵和一个整数 k。我们需要找到矩阵中一个矩形的最大和，使得它的和不大于 k。因此，如果输入为 −
| 1 | 0 | 1 |
| 0 | -3 | 2 |
k = 3，则输出为 3，因为标记矩形的和为 3。
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个函数 maxSumSubmatrix()，该函数接受一个二维数组矩阵和 k，
- n := 行号，m := 列号
- ans := -inf
- 初始化 l := 0，当 l < m，更新(将 l 增加 1)，执行 −
- 定义一个大小为 n 的数组 rowSum
- 初始化 r := l，当 r < m 时，更新(将 r 增加 1)，执行 −
- 初始化 i := 0，当 i < n 时，更新(将 i 增加 1)，执行 −
- rowSum[i] := rowSum[i] + matrix[i, r]
- 定义一个集合 s
- 将 0 插入 s
- currSum := 0
- 初始化 i := 0，当 i < n，更新(将 i 加 1)，执行 −
- currSum := currSum + rowSum[i]
- it := 集合中第一个不大于 currSum 的元素 - k
- 如果它不等于 s 的最后一个元素，则 −
- ans := ans 和 (currSum - it) 中的最大值
- 将 currSum 插入 s
- 初始化 i := 0，当 i < n 时，更新(将 i 增加 1)，执行 −
- return 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
