ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে দেওয়া, কাজটি হল সমস্ত অনন্য উপাদান ধারণকারী একটি সাবয়ারে মুছে ফেলা। সাবারে মুছে দিয়ে আপনি যা পাবেন তা এর উপাদানগুলির যোগফলের সমান৷
৷এর আগে বা পরে শর্তগুলি মুছে দিয়ে বর্তমান সাবয়ারের সর্বাধিক যোগফল ফেরত দিন, আমরা ঠিক একটি সাব্যারে মুছে দিয়ে সর্বাধিক যোগফল পেতে পারি৷
একটি অ্যারে 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}৷
এই সমস্যা সমাধানের পদ্ধতি
এই সমস্যা সমাধানের জন্য, আমরা একটি স্লাইডিং উইন্ডোর ধারণা ব্যবহার করব। এই কৌশলটি দেখায় কিভাবে একটি নেস্টেড লুপকে একটি একক লুপে রূপান্তরিত করা যায় যাতে সময়ের জটিলতা কম হয়৷
এই কৌশলে, আমরা প্রথমে দুটি পয়েন্টার (বাম এবং ডান) এবং উইন্ডোর আকারকে 'উইন' হিসাবে শুরু করব। অ্যারের মাধ্যমে পুনরাবৃত্তি করার সময় আমরা একটি নির্দিষ্ট জয়ের আকার সর্বাধিক কিনা তা পরীক্ষা করব। যদি আমরা এটি সর্বাধিক খুঁজে পাই, আমরা এটি আউটপুট হিসাবে ফেরত দেব।
এই সমস্যা সমাধানের পদ্ধতি,
-
ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে ইনপুট নিন।
-
একটি পূর্ণসংখ্যা ফাংশন সর্বাধিকUniqueSubarray(ভেক্টর&arr) ইনপুট হিসাবে একটি অ্যারে নেয়।
-
তিন-পয়েন্টার 'I', 'j' এবং উইন্ডোর আকার 'win' নিয়ে অ্যারের উপর পুনরাবৃত্তি করুন এবং হ্যাশসেটে একটি উপাদান সহ বর্তমান উইন্ডোটি উপস্থিত আছে কিনা তা খুঁজে বের করুন তারপর উইন্ডোটি সরান এবং আবার অন্য একটি উপাদানের জন্য পরীক্ষা করুন। যদি এটি উপস্থিত না থাকে, তাহলে এটি হ্যাশসেটে ঢোকান এবং উইন্ডোর আকার হ্রাস করুন যা পূর্ববর্তী উপাদানটিকে সরিয়ে দেয়৷
-
ফলাফল এবং উইন্ডো মান সর্বোচ্চ খুঁজুন.
-
ফলাফল ফেরত দিন।
উদাহরণ
#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
