C++-এ দুটি অ্যারে থেকে ইউনিক উইন্ডো কন্ডিশনে সর্বোচ্চ সম বের করার প্রোগ্রাম

সমস্যা বিবরণ

দুটি সমান আকারের অ্যারে A এবং B দেওয়া থাকলে, B-এ একটি উইন্ডো (সাবঅ্যারে) খুঁজে বের করতে হবে যাতে A-এ একই উইন্ডোর এলিমেন্টগুলো ইউনিক (unique) হয় এবং B-এ সেই উইন্ডোর সম সর্বোচ্চ হয়।

সমাধানের পদ্ধতি (Sliding Window + Hash Set)

1. স্লাইডিং উইন্ডো ব্যবহার করুন: curr_begin এবং i।
2. সেট mp রাখুন A-এ উইন্ডোর এলিমেন্টগুলো ট্র্যাক করার জন্য।
3. i বেড়াতে থাকুন:
   • যদি A[i] ইতিমধ্যে সেটে থাকে, তবে curr_begin বেড়াতে থাকুন যতক্ষন না ইউনিক হয়।
   • B[curr_begin] বিয়োগ করুন কারেন্ট সম থেকে।
4. A[i] সেটে যোগ করুন, B[i] যোগ করুন কারেন্ট সমে।
5. সর্বোচ্চ সম আপডেট করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

int returnMaxSum(int A[], int B[], int n) {
    unordered_set mp;
    int result = 0;
    int curr_sum = 0, curr_begin = 0;
    for (int i = 0; i < n; ++i) {
        while (mp.find(A[i]) != mp.end()) {
            mp.erase(A[curr_begin]);
            curr_sum -= B[curr_begin];
            curr_begin++;
        }
        mp.insert(A[i]);
        curr_sum += B[i];
        result = max(result, curr_sum);
    }
    return result;
}

int main() {
    int A[] = {0, 1, 2, 3, 0, 1, 4};
    int B[] = {9, 8, 1, 2, 3, 4, 5};
    int n = sizeof(A) / sizeof(A[0]);
    cout << returnMaxSum(A, B, n);
    return 0;
}

আউটপুট

20

ব্যাখ্যা

উইন্ডো: A[2..6] = {2,3,0,1,4} (ইউনিক), B[2..6] = {1,2,3,4,5} → সম = 15? Wait, output 20. Let me recheck: A[0..3]={0,1,2,3}, B[0..3]={9,8,1,2}=20. Yes, first 4 elements unique in A.

জটিলতা

• সময়: O(n)
• স্থান: O(n)