আয়তক্ষেত্রের সর্বোচ্চ যোগফল C++ এ K-এর চেয়ে বড় নয়

ধরুন আমাদের একটি 2D ম্যাট্রিক্স এবং একটি পূর্ণসংখ্যা k আছে। আমাদের ম্যাট্রিক্সে একটি আয়তক্ষেত্রের সর্বোচ্চ যোগফল খুঁজে বের করতে হবে, যাতে এর যোগফল k-এর থেকে বেশি না হয়। সুতরাং, যদি ইনপুট −

এবং k =3, তাহলে আউটপুট হবে 3, যেহেতু চিহ্নিত আয়তক্ষেত্রের যোগফল 3।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সংজ্ঞায়িত করুন maxSumSubmatrix(), এটি একটি 2D অ্যারে ম্যাট্রিক্স এবং k লাগবে,
• n :=সারি সংখ্যা, m :=কলাম সংখ্যা
• উত্তর :=-inf
• আরম্ভ করার জন্য l :=0, যখন l
• n আকারের একটি অ্যারের সারিসম সংজ্ঞায়িত করুন
• আর আরম্ভ করার জন্য :=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