सकारात्मक पूर्णांकों की एक सरणी दी गई है, कार्य एक सबएरे को मिटाना है जिसमें सभी अद्वितीय तत्व हों। सबएरे को मिटाकर आपको जो मिलता है वह उसके तत्वों का योग के बराबर होता है।
वर्तमान सबएरे के अधिकतम योग को उसके पहले या बाद के पदों को मिटाकर लौटाएं, हम ठीक एक सबएरे को मिटाकर अधिकतम योग प्राप्त कर सकते हैं।
एक सरणी arr को a का सबएरे कहा जाता है यदि यह a का एक सन्निहित उपअनुक्रम बनाता है अर्थात यदि यह कुछ (l, r) के लिए a[l], a[l+1],..., a[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} है।
इस प्रॉब्लम को हल करने का दृष्टिकोण
इस प्रॉब्लम को हल करने के लिए, हम स्लाइडिंग विंडो की अवधारणा का उपयोग करेंगे। यह तकनीक दिखाती है कि कैसे एक नेस्टेड लूप को एक सिंगल लूप में बदला जा सकता है ताकि समय जटिलता कम हो सके।
इस तकनीक में, हम पहले दो पॉइंटर्स (लेफ्ट और राइट) और विंडो के आकार को 'विन' के रूप में इनिशियलाइज़ करेंगे। सरणी के माध्यम से पुनरावृति करते समय हम जांचेंगे कि क्या किसी विशेष विन का आकार अधिकतम है या नहीं। यदि हम इसे अधिकतम पाते हैं, तो हम इसे आउटपुट के रूप में लौटाएंगे।
इस प्रॉब्लम को हल करने का दृष्टिकोण,
सकारात्मक पूर्णांकों की एक सरणी का इनपुट लें।
एक पूर्णांक फंक्शन maximumUniqueSubarray(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 = {5, 3, 1, 3, 5, 3, 1, 3, 5};
cout << maximumUniqueSubarray(nums) << endl;
return 0;
}
आउटपुट
उपरोक्त कोड चलाने पर निम्न आउटपुट उत्पन्न होगा,
9
