সি++-এ দূরত্ব k মেনে সাবসিকোয়েন্সের সর্বোচ্চ যোগফল বের করা

সমস্যা বিবরণ

একটি অ্যারে arr[] এবং ইন্টিজার k দেওয়া আছে। এমন সাবসিকোয়েন্স খুঁজে বের করতে হবে যাতে যেকোনো দুটি উপাদানের ইনডেক্স পার্থক্য k-এর চেয়ে কম নয় (অর্থাৎ কমপক্ষে k দূরত্বে থাকে), এবং যোগফল সর্বোচ্চ হয়।

উদাহরণ: arr = {6,2,5,1,9,11,4}, k = 2 → আউটপুট 16 (সাবসিকোয়েন্স: {5,11})।

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

ডাইনামিক প্রোগ্রামিং:

1. maxSumDP[i] = ইনডেক্স i পর্যন্ত বিবেচনা করলে সর্বোচ্চ যোগফল।
2. বেস: maxSumDP[0] = arr[0]।
3. ট্রানজিশন:
   • যদি i < k: maxSumDP[i] = max(arr[i], maxSumDP[i-1])
   • অন্যথায়: maxSumDP[i] = max(arr[i], maxSumDP[i-(k+1)] + arr[i])
4. সর্বোচ্চ maxSumDP[i] রিটার্ন করুন।

উদাহরণ কোড

#include <iostream>
using namespace std;

int retMaxVal(int a, int b) { return a > b ? a : b; }

int calcMaxSumSubSeq(int arr[], int k, int n) {
    int maxSumDP[n];
    int maxSum = -1;
    maxSumDP[0] = arr[0];
    for (int i = 1; i < n; i++) {
        if (i < k)
            maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i-1]);
        else
            maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i-(k+1)] + arr[i]);
    }
    for (int i = 0; i < n; i++)
        maxSum = retMaxVal(maxSumDP[i], maxSum);
    return maxSum;
}

int main() {
    int arr[] = {6, 2, 5, 1, 9, 11, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 2;
    cout << "The maximum sum possible for a sub-sequence such that no two elements appear at a distance < " << k << " in the array is " << calcMaxSumSubSeq(arr, k, n);
    return 0;
}

আউটপুট

The maximum sum possible for a sub-sequence such that no two elements appear at a distance < 2 in the array is 16