C++でKより大きくない長方形の最大合計

2D行列と整数kがあるとします。合計がkを超えないように、行列内の長方形の最大合計を見つける必要があります。したがって、入力が-

また、k =3の場合、マークされた長方形の合計は3であるため、出力は3になります。

これを解決するには、次の手順に従います-

• 関数maxSumSubmatrix（）を定義します。これには、1つの2D配列行列とkが必要です。
• n：=行番号、m：=列番号
• ans：=-inf
• 初期化l：=0の場合、l
• サイズnの配列rowSumを定義します
• rを初期化する場合：=l、r
• iを初期化する場合：=0、i
• rowSum [i]：=rowSum [i] + matrix [i、r]

理解を深めるために、次の実装を見てみましょう-

例

#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