একটি অ্যারে দেওয়া আছে। এমন সাবসিকোয়েন্স বের করতে হবে যাতে কোনো দুটি উপাদান আডজেসেন্ট না হয় এবং তাদের যোগফল সর্বোচ্চ হয়। ডাইনামিক প্রোগ্রামিং পদ্ধতি।
উদাহরণ
arr[] = {5, 1, 3, 7, 9, 2, 5}
আউটপুট: 22
ব্যাখ্যা: ইন্ডেক্স ০,২,৪,৬: 5+3+9+5 = 22।
DP রিলেশন
DP[i] = max( DP[i+1], arr[i] + DP[i+2] )
মেমোইজেশন দিয়ে টপ-ডাউন বা বটম-আপ করা যায়।
C++ প্রোগ্রাম (মেমোইজেশন)
#include <iostream>
using namespace std;
int DP[100];
bool visited[100];
int maxVal(int a, int b) { return (a > b) ? a : b; }
int calcMaxSumWOAdj(int arr[], int i, int n) {
if (i >= n) return 0;
if (visited[i]) return DP[i];
visited[i] = true;
DP[i] = maxVal(calcMaxSumWOAdj(arr, i+1, n), arr[i] + calcMaxSumWOAdj(arr, i+2, n));
return DP[i];
}
int main() {
int arr[] = {5, 1, 3, 7, 9, 2, 5};
int n = sizeof(arr)/sizeof(int);
cout << "Max sum without adjacent: " << calcMaxSumWOAdj(arr, 0, n);
return 0;
}
আউটপুট: Max sum without adjacent: 22
