সমস্যা বিবরণ
একটি অ্যারে arr[] এবং সংখ্যা k দেওয়া আছে। এমন সাবসিকোয়েন্স খুঁজে বের করতে হবে যাতে যেকোনো দুটি উপাদানের ইনডেক্স পার্থক্য কমপক্ষে k হয়, এবং যোগফল সর্বোচ্চ হয়।
উদাহরণ: arr = {2,3,7,9,2,8,3}, k=2 → আউটপুট 15 (সাবসিকোয়েন্স: {7,8})।
সমাধানের পদ্ধতি
ডাইনামিক প্রোগ্রামিং:
maxSumDP[i]= ইনডেক্সiথেকে শেষ পর্যন্ত শর্ত পূরণকারী সাবসিকোয়েন্সের সর্বোচ্চ যোগফল।- বেস:
maxSumDP[n-1] = arr[n-1]। - ট্রানজিশন:
- যদি
i + k + 1 >= n:maxSumDP[i] = max(arr[i], maxSumDP[i+1]) - অন্যথায়:
maxSumDP[i] = max(arr[i] + maxSumDP[i+k+1], maxSumDP[i+1])
- যদি
i = n-2থেকে0পর্যন্ত পূরণ করুন।maxSumDP[0]রিটার্ন করুন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int calcMaxSubSeqSum(int arr[], int N, int k) {
int maxSumDP[N];
maxSumDP[N-1] = arr[N-1];
for (int i = N-2; i >= 0; i--) {
if (i + k + 1 >= N)
maxSumDP[i] = max(arr[i], maxSumDP[i+1]);
else
maxSumDP[i] = max(arr[i] + maxSumDP[i+k+1], maxSumDP[i+1]);
}
return maxSumDP[0];
}
int main() {
int N = 10, k = 2;
int arr[] = {50, 70, 40, 50, 90, 70, 60, 40, 70, 50};
cout << "The maximum sum subsequence with at-least k distant elements is " << calcMaxSubSeqSum(arr, N, k);
return 0;
}
আউটপুট
The maximum sum subsequence with at-least k distant elements is 230
