C++-এ স্লাইডিং উইন্ডো দিয়ে সর্বোচ্চ ইরেজার ভ্যালু বের করা

পজিটিভ ইন্টিজারের একটি অ্যারে দেওয়া থাকলে, একটি সাবঅ্যারে ইরেজ (মুছে ফেলা) করতে হবে যাতে সাবঅ্যারেটির সব উপাদান ইউনিক থাকে। ইরেজ করার পর পাওয়া মান হবে সাবঅ্যারেটির উপাদানগুলোর যোগফল। এই যোগফল সর্বোচ্চ করতে হবে।

ইনপুট-১

arr[] = {1, 2, 4, 5, 6}

আউটপুট

ব্যাখ্যা

অপ্টিমাল সাবঅ্যারে {2, 4, 5, 6} যার যোগফল ১৭।

ইনপুট-২

arr[] = {5, 3, 1, 3, 5, 3, 1, 3, 5}

আউটপুট

সমাধানের পদ্ধতি

স্লাইডিং উইন্ডো (Sliding Window) টেকনিক ব্যবহার করে O(n) সময়ে সমাধান করা যায়।

দুই পয়েন্টার i (left) এবং j (right) এবং উইন্ডো যোগফল win নিন।
একটি unordered_set দিয়ে উইন্ডোয়ের ইউনিক উপাদান ট্র্যাক করুন।
j বেড়াতে থাকুন। যদি arr[j] সেটে থাকে, তবে i বেড়িয়ে সেট থেকে arr[i] মুছুন এবং win কমানো।
নতুন এলিমেন্ট সেটে যোগ করুন, win বেড়ান।
result = max(result, 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 = {5, 3, 1, 3, 5, 3, 1, 3, 5};
    cout << maximumUniqueSubarray(nums) << endl;
    return 0;
}