मान लीजिए कि हमने एन पूर्णांकों की एक सरणी दी है, जिसका कार्य अधिकतम लंबाई वाले उप-सरणी की लंबाई का पता लगाना है। यदि कोई सबअरे नहीं है जिसकी लंबाई अधिकतम है या योग 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
योग =0 वाला सबसे बड़ा उप-सरणी {-2, 2, -8, 1, 7} है। इस प्रकार, सबसे बड़े उप-सरणी की लंबाई '5' है।