मान लीजिए कि हमारे पास एक द्विआधारी सरणी है, हमें 0 और 1 की समान संख्या के साथ एक सन्निहित उपसरणी की अधिकतम लंबाई ज्ञात करनी है। इसलिए यदि इनपुट [0,1,0] जैसा है, तो आउटपुट 2 के रूप में [0 होगा, 1] या [1,0] 0 और 1 की समान संख्या वाली सबसे बड़ी सन्निहित सरणी है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- ret:=0, n:=अंकों का आकार, योग:=0
- नक्शा m बनाएं, m सेट करें[0] :=- 1
- मैं के लिए 0 से लेकर अंकों के आकार तक - 1
- योग :=योग + 1 जब अंक [i] 1 है अन्यथा योग :=योग – 1
- यदि योग m में है, तो ret :=ret का अधिकतम और i – m[sum], अन्यथा m[sum] :=i
- रिटर्न रिटर्न
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int ret = 0;
int n = nums.size();
int sum = 0;
map <int, int> m;
m[0] = -1;
for(int i = 0; i < nums.size(); i++){
sum += nums[i] == 1 ? 1: -1;
if(m.count(sum)){
ret = max(ret, i - m[sum]);
}else m[sum] = i;
}
return ret;
}
};
main(){
vector<int> v = {0,1,0,0,1};
Solution ob;
cout << (ob.findMaxLength(v));
} इनपुट
[0,1,0,0,1]
आउटपुट
4