सकारात्मक पूर्णांकों की एक सरणी को देखते हुए, कार्य सभी अद्वितीय तत्वों वाले एक उपसरणी को मिटाना है। सबएरे को मिटाकर आपको जो मिलता है वह उसके तत्वों के योग के बराबर होता है।
इसके पहले या बाद की शर्तों को मिटाकर वर्तमान सबअरे का अधिकतम योग लौटाएं, हम ठीक एक सबएरे को मिटाकर अधिकतम योग प्राप्त कर सकते हैं।
एक सरणी गिरफ्तारी a . का उप-सरणी कहा जाता है यदि यह a . का एक सन्निहित अनुवर्ती बनाता है अगर यह बराबर है a[l], a[l+1],..., a[r] कुछ के लिए (l,r)। उदाहरण के लिए,
इनपुट-1 -
arr[ ] = { 1,2,4,5,6 } आउटपुट -
17
स्पष्टीकरण - इष्टतम उपसरणी {2,4,5,6} है।
इनपुट-2 -
arr[ ]= {5,3,1,3,5,3,1,3,5} आउटपुट -
9
स्पष्टीकरण - इष्टतम उपसरणी {5,3,1} या {1,3,5} है।
इस समस्या को हल करने का तरीका
इस समस्या को हल करने के लिए, हम स्लाइडिंग विंडो की अवधारणा का उपयोग करेंगे। यह तकनीक दिखाती है कि समय की जटिलता को कम करने के लिए नेस्टेड लूप को एकल लूप में कैसे बदला जा सकता है।
इस तकनीक में, हम पहले दो पॉइंटर्स (बाएं और दाएं) और विंडो के आकार को 'जीत' के रूप में प्रारंभ करेंगे। सरणी के माध्यम से पुनरावृत्ति करते समय हम जांच करेंगे कि किसी विशेष जीत का आकार अधिकतम है या नहीं। यदि हम इसे अधिकतम पाते हैं, तो हम इसे आउटपुट के रूप में वापस कर देंगे।
इस समस्या को हल करने का तरीका,
-
सकारात्मक पूर्णांकों की एक सरणी इनपुट करें।
-
एक पूर्णांक फ़ंक्शन maxUniqueSubarray(vector&arr) इनपुट के रूप में एक सरणी लेता है।
-
तीन-पॉइंटर्स 'I', 'j' और विंडो साइज 'जीत' लेना और ऐरे पर पुनरावृत्ति करना और यह पता लगाना कि क्या वर्तमान विंडो में एक तत्व हैशसेट में मौजूद है, फिर विंडो को स्थानांतरित करें और फिर से किसी अन्य तत्व की जांच करें। यदि यह मौजूद नहीं है, तो इसे हैशसेट में डालें और विंडो का आकार घटाएं जो पिछले तत्व को हटा देता है।
-
परिणाम और विंडो मान में अधिकतम खोजें।
-
परिणाम लौटाएं।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
int maximumUniqueSubarray(vector<int>& arr) {
int result = 0;
unordered_set<int> hashset;
for (int i = 0, j = 0, win = 0; j < arr.size(); j++) {
while (hashset.find(arr[j]) != hashset.end()) {
hashset.erase(arr[i]);
win -= arr[i];
i++;
}
hashset.insert(arr[j]);
win += arr[j];
result = max(result, win);
}
return result;
}
int main(){
vector<int>nums;
nums<<5,3,1,3,5,3,1,3,5;
cout<<maximumUniqueSubarray(nums)<<endl;
return 0;
} आउटपुट
उपरोक्त कोड को चलाने से आउटपुट इस प्रकार उत्पन्न होगा,
9