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

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

1	0	1
0	-3	2

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

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

एक फ़ंक्शन maxSumSubmatrix() परिभाषित करें, जो एक 2D सरणी matrix और 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 परिभाषित करें
- s में 0 डालें
- currSum := 0
- i := 0 से आरंभ करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), करें -
  - currSum := currSum + rowSum[i]
  - it := सेट का पहला तत्व जो currSum - k से बड़ा नहीं है
  - यदि यह s के अंतिम तत्व के बराबर नहीं है, तो -
    - ans := ans और (currSum - it) का अधिकतम
  - currSum को s में डालें
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