নির্দিষ্ট পার্থক্য সহ জোড়ার সর্বোচ্চ যোগফল (C++ প্রোগ্রাম)

আমরা এমনভাবে জোড়া খুঁজে বের করব যেন জোড়া উপাদানগুলোর পার্থক্য d-এর চেয়ে কম হয়। সকল এমন জোড়ার যোগফল সর্বোচ্চ হতে হবে।

arr[] = {5, 9, 11, 7, 2, 12, 3} d = 5

47

সর্বোচ্চ যোগফলে অবদানকারী জোড়াগুলো: (3, 5), (7, 9), (11, 12)
যোগফল = 3 + 5 + 7 + 9 + 11 + 12 = 47

একটি সহজ এবং স্পষ্ট সমাধান হল অ্যারেতে সকল বৈধ জোড়া তৈরি করে তাদের যোগফল বের করা এবং সর্বোচ্চ যোগফল ফেরত দেওয়া। কিন্তু এই সমাধান দক্ষ নয়।

একটি দক্ষ সমাধান হল ডাইনামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করা। এখানে, আমরা সর্বোচ্চ যোগফল গঠনকারী সর্বোত্তম জোড়াগুলো খুঁজে বের করব। এর জন্য আমরা একটি সর্ট করা অ্যারে ব্যবহার করব, তাই প্রথমে দেওয়া অ্যারেটি সর্ট করব এবং তারপর সেটিতে কাজ করব। যোগফল বের করার জন্য, আমরা একটি অ্যারে ব্যবহার করব যা বর্তমান উপাদান পর্যন্ত জোড়ার সর্বোচ্চ যোগফল সংরক্ষণ করবে। এর জন্য, আমরা চেক করব বর্তমান উপাদান এবং আগের উপাদান জোড়া তৈরি করে কিনা। যদি হ্যাঁ, তবে আমরা জোড়ার যোগফল 지금까지의 অ্যারেতে সর্বোচ্চ যোগফলের সাথে যোগ করব। অন্যথায়, সর্বোচ্চ যোগফল অপরিবর্তিত থাকবে।

আরম্ভিকরণ: DP[n]

ধাপ ১: অ্যারে arr[]-এর জন্য।

ধাপ ২: DP[0] = 0;

ধাপ ৩: i → 1 থেকে n পর্যন্ত লুপ।

ধাপ ৩.১: আগের উপাদানের সাথে জোড়া সম্ভব কিনা চেক করুন: if(arr[i] - arr[i-1] < d)।

ধাপ ৩.২: যদি হ্যাঁ, তবে চেক করুন বর্তমান জোড়ার যোগফল শেষ বিবেচিত যোগফল থেকে বড় কিনা এবং সর্বোচ্চ মান বর্তমান যোগফলে যোগ করুন। অর্থাৎ if((DP[i-2] + arr[i-1] + arr[i]) > (DP[i-1])) → DP[i] = (DP[i-2] + arr[i-1] + arr[i]), অন্যথায় DP[i] = DP[i-1]।

ধাপ ৩.৩: i = 1 এর জন্য একটি ব্যতিক্রম, যেখানে DP[i-2] কোনো মান সম্ভব নয়, এই ক্ষেত্রে DP[i-2] বিবেচনা করা হবে না কারণ এটি প্রথম জোড়ার যোগফল।

ধাপ ৪: DP[n-1] ফেরত দিন।

#include 
using namespace std;

int CalcmaxPairSum(int arr[], int n, int d) {
    sort(arr, arr + n);
    int maxSumDP[n];
    maxSumDP[0] = 0;
    for (int i = 1; i < n; i++) {
        maxSumDP[i] = maxSumDP[i - 1];
        if (arr[i] - arr[i - 1] < d) {
            if (i >= 2)
                if (maxSumDP[i] < (maxSumDP[i - 2] + arr[i - 1] + arr[i]))
                    maxSumDP[i] = (maxSumDP[i - 2] + arr[i - 1] + arr[i]);
            else
                if (maxSumDP[i] < (arr[i - 1] + arr[i]))
                    maxSumDP[i] = arr[i - 1] + arr[i];
        }
    }
    return maxSumDP[n - 1];
}

int main() {
    int arr[] = {5, 9, 11, 7, 2, 12, 3};
    int n = 7, d = 5;
    cout << "The maximum sum of pairs with specific difference is " << CalcmaxPairSum(arr, n, d);
    return 0;
}

The maximum sum of pairs with specific difference is 47