সি++-এ অ্যাডজেসেন্ট এলিমেন্ট নেই এমন সর্বোচ্চ সাবসিকোয়েন্স যোগফল (অল্টারনেট মেথড)

সমস্যা বিবরণ

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

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

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

ডাইনামিক প্রোগ্রামিং (বটম-আপ):

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

উদাহরণ কোড

#include <iostream>
using namespace std;

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

int calcMaxSum(int arr[], int n) {
    int maxSumDP[n];
    maxSumDP[n-1] = arr[n-1];
    maxSumDP[n-2] = max(arr[n-1], arr[n-2]);
    for (int i = n-3; i >= 0; i--)
        maxSumDP[i] = retMaxVal(arr[i] + maxSumDP[i+2], maxSumDP[i+1]);
    return maxSumDP[0];
}

int main() {
    int arr[] = {5, 2, 1, 9, 6};
    int n = sizeof(arr)/sizeof(int);
    cout << "The maximum subsequence sum... is " << calcMaxSum(arr, n);
    return 0;
}

আউটপুট

The maximum subsequence sum in such a way that no two consecutive elements of the array is 14