आयत का अधिकतम योग C++ में K से बड़ा नहीं है

मान लीजिए कि हमारे पास एक 2D मैट्रिक्स है, और एक पूर्णांक k है। हमें मैट्रिक्स में एक आयत का अधिकतम योग ज्ञात करना है, जैसे कि इसका योग k से अधिक न हो। तो, अगर इनपुट इस तरह है -

और k =3, तो आउटपुट 3 होगा, क्योंकि चिह्नित आयत का योग 3 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें maxSumSubmatrix(), यह एक 2D सरणी मैट्रिक्स और k लेगा,
• n :=पंक्ति संख्या, m :=स्तंभ संख्या
• उत्तर:=-इन्फ
• इनिशियलाइज़ l :=0 के लिए, जब l
• एक सरणी पंक्ति परिभाषित करेंआकार n का योग
• आर शुरू करने के लिए :=l, जब r
• इनिशियलाइज़ i :=0 के लिए, जब i करें
• rowSum[i] :=rowSum[i] + मैट्रिक्स[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