C++-এ নির্দিষ্ট পার্থক্য কম থাকা জোড়ার সর্বোচ্চ সম বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি অ্যারে এবং মান K দেওয়া থাকলে, পার্থক্য K-র চেয়ে কম হয় এমন জোড়া বানান (disjoint sets) এবং তাদের মোট সম সর্বোচ্চ করুন।

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

1. অ্যারে সর্ট করুন।
2. dp[i] = প্রথম i+1 এলিমেন্ট ব্যবহার করে সর্বোচ্চ সম।
3. dp[0] = 0।
4. i = 1 থেকে N-1:
   • dp[i] = dp[i-1] (i-তম এলিমেন্ট নাও নিলে)۔
   • যদি arr[i] - arr[i-1] < K হয়:
     • i>=2 হলে: dp[i] = max(dp[i], dp[i-2] + arr[i] + arr[i-1])
     • অন্যথায়: dp[i] = max(dp[i], arr[i] + arr[i-1])
5. dp[N-1] রিটার্ন করুন।

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

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

int maxSumPairWithDifferenceLessThanK(int arr[], int N, int K) {
    sort(arr, arr + N);
    int dp[N];
    dp[0] = 0;
    for (int i = 1; i < N; i++) {
        dp[i] = dp[i - 1];
        if (arr[i] - arr[i - 1] < K) {
            if (i >= 2)
                dp[i] = max(dp[i], dp[i - 2] + arr[i] + arr[i - 1]);
            else
                dp[i] = max(dp[i], arr[i] + arr[i - 1]);
        }
    }
    return dp[N - 1];
}

int main() {
    int arr[] = {3, 5, 10, 15, 17, 12, 9};
    int N = sizeof(arr) / sizeof(int);
    int K = 4;
    cout << maxSumPairWithDifferenceLessThanK(arr, N, K);
    return 0;
}

আউটপুট

62

ব্যাখ্যা

সর্টেড: [3,5,9,10,12,15,17]

জোড়া: (3,5)=8, (9,10)=19, (15,17)=32 → মোট 59? Wait, recheck: DP gives 62. জোড়া হতে পারে (10,12)=22, (15,17)=32, (3,5)=8 → 62।

জটিলতা

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