ধরুন আমাদের একটি বাইনারি অ্যারে আছে, আমাদের ০ এবং ১ সমান সংখ্যক আছে এমন সন্নিহিত সাবঅ্যারেতে সর্বোচ্চ দৈর্ঘ্য বের করতে হবে। তাই যদি ইনপুট হয় [0,1,0], তবে আউটপুট হবে ২ কারণ [0,1] বা [1,0] ০ এবং ১ সমান সংখ্যক সহ সর্বোচ্চ সন্নিহিত অ্যারে।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- ret := ০, n := nums-এর আকার, sum := ০
- একটি ম্যাপ m তৈরি করুন, m[0] := - ১ সেট করুন
- i = 0 থেকে nums-এর আকার – ১ পর্যন্ত
- sum := sum + 1 যখন nums[i] 1 হয় অন্যথায় sum := sum – 1
- যদি sum m-এ থাকে, তবে ret := ret এবং i – m[sum]-এর max, অন্যথায় m[sum] := i
- ret ফেরত দিন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন −
উদাহরণ
#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
