ধরুন আমাদের একটি বাইনারি অ্যারে আছে, আমাদের 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
