在C ++中，矩形的最大和不大于K

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个2D矩阵和一个整数k。我们必须找到矩阵中矩形的最大和，以使其总和不大于k。所以，如果输入像-

101
0-32

且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

    以上是 在C ++中，矩形的最大和不大于K 的全部内容， 来源链接： utcz.com/z/338328.html

    回到顶部