ধরুন আমরা N পূর্ণসংখ্যার একটি অ্যারে দিয়েছি যার কাজটি হল সর্বাধিক দৈর্ঘ্য বিশিষ্ট সাবয়ারের দৈর্ঘ্য খুঁজে বের করা। যদি এমন কোনো সাবয়ারে না থাকে যার দৈর্ঘ্য সর্বাধিক বা যোগফল 0 এর সমান হয় তবে '0' ফেরত দিন। উদাহরণস্বরূপ,
ইনপুট-1 −
N = 8
A[ ] = {15, -5, -1, 5,1, 4 } আউটপুট −
4
ব্যাখ্যা − শূন্য-সমষ্টি সহ বৃহত্তম সাবঅ্যারে হল { -5, -1, 5, 1} যার দৈর্ঘ্য 4।
ইনপুট-2 −
N = 5
A[ ] = {3, 2 ,4, 8, -1} আউটপুট −
0
ব্যাখ্যা − যেহেতু সেখানে কোনো সাব্যারে নেই যার যোগফল শূন্যের সমান, আউটপুট হল '0'৷
এই সমস্যা সমাধানের পদ্ধতি
এই বিশেষ সমস্যা সমাধানের জন্য বিভিন্ন পন্থা আছে। রৈখিক সময়ে O(n) সমাধান করার জন্য সবচেয়ে উপযুক্ত অ্যালগরিদম হল একটি হ্যাশ টেবিল ব্যবহার করে।
ধারণাটি হল একটি হ্যাশ টেবিল তৈরি করা যা সমস্ত সাবয়ারের সমষ্টি সংরক্ষণ করে যার যোগফল কী হিসাবে সংরক্ষণ করা হয় এবং মান হিসাবে সূচক।
আমরা প্রথমে পুরো অ্যারে অতিক্রম করব এবং বর্তমান যোগফল সংরক্ষণ করব। বর্তমান যোগফল হ্যাশ টেবিলে পাওয়া যাচ্ছে কি না তা আমরা পরীক্ষা করব। যদি এটি হ্যাশটেবলে উপস্থিত থাকে, তাহলে সাবয়ারের সর্বাধিক দৈর্ঘ্য আপডেট করুন।
-
অ্যারের N আকারের ইনপুট নিন।
-
একটি ফাংশন lenMax(int *arr, int size) একটি অ্যারে এবং এর আকারকে ইনপুট হিসাবে নেয় যা শূন্য সমন্বিত সাবয়ারের সর্বাধিক দৈর্ঘ্য প্রদান করে।
-
পূর্ণসংখ্যার একটি ক্রমবিন্যস্ত মানচিত্র যাতে যোগফল হিসাবে কী এবং সূচক হিসাবে মান থাকে তা পরীক্ষা করে যে কোনো যোগফল পুনরাবৃত্তি হচ্ছে কিনা।
-
অ্যারের উপাদানটির উপর পুনরাবৃত্তি করা এবং হ্যাশটেবলে যোগফল উপস্থিত থাকলে অ্যারের বর্তমান যোগফল খুঁজে বের করা, তারপর সাবয়ারের সর্বাধিক দৈর্ঘ্য খুঁজুন। যদি না হয়, তাহলে নতুন যোগফল এবং এর সূচক সহ হ্যাশটেবলে ঢোকান।
-
আউটপুট হিসাবে সর্বাধিক দৈর্ঘ্য ফেরত দিন।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
int lenMax(int *arr, int size){
unordered_map<int,int>mp;
int sum=0;
int maxlen=0;
for(int i=0;i<size;i++){
sum+=arr[i];
if(arr[i]==0 && maxlen==0){
maxlen=1;
}
if(sum==0){
maxlen=i+1;
}
if(mp.find(sum)!= mp.end()){
maxlen= max(maxlen, i-mp[sum]);
} else {
mp[sum]=i;
}
}
return maxlen;
}
int main(){
int N=6;
int A[N]={15,-2,2,-8,1,7,10,23};
cout<<lenMax(A,N)<<endl;
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই, তাহলে এটি আউটপুটটিকে
হিসাবে প্রিন্ট করবে5
sum=0 সহ বৃহত্তম সাবঅ্যারে হল {-2, 2, -8, 1, 7}। এইভাবে, বৃহত্তম সাবয়ারের দৈর্ঘ্য হল '5'৷
৷