এই সমস্যায়, আমাদের n আকারের একটি অ্যারে অ্যারে [] এবং একটি সংখ্যা k দেওয়া হয়েছে। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যাতে অন্তত দূরবর্তী উপাদানের সাথে সর্বাধিক যোগফল বের করা যায়।
সমস্যা বর্ণনা − আমাদের সাবয়ারের সমষ্টি খুঁজে বের করতে হবে যাতে সাবয়ারের উপাদানগুলি অ্যারের থেকে নেওয়া হয় যার সূচক k দূরত্বে থাকে এবং যোগফল সর্বাধিক হয়৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {2, 3, 7, 9, 2, 8, 3} আউটপুট
15
ব্যাখ্যা
All subsequences that satisfy the given condition,
{2, 9, 3}, Sum = 14
{3, 2}, Sum = 5
{7, 8}, Sum = 15 সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল প্রদত্ত শর্ত পূরণকারী সমস্ত সম্ভাব্য সাব্যারে খুঁজে বের করা। সমস্ত অ্যারের যোগফল খুঁজুন এবং সবগুলির সর্বাধিক ফেরত দিন৷
৷বর্তমান উপাদান পর্যন্ত সর্বাধিক যোগফল সংরক্ষণ করার জন্য একটি অ্যারে তৈরি করে একটি গতিশীল প্রোগ্রামিং পদ্ধতি ব্যবহার করে সমস্যার একটি আরও কার্যকর সমাধান। বর্তমান উপাদানের জন্য, আমরা হয় এটিকে যোগফলের জন্য বিবেচনা করতে পারি বা যোগফলের জন্য বাতিল করতে পারি, বর্তমান সূচক পর্যন্ত যোগফল যেটি বাড়ে।
যদি আমরা যোগফলের জন্য বিবেচনা করি, যোগফল[i] =যোগফল[i + k + 1] + arr[i+1] অন্যথায় যোগফলের জন্য এটি বাতিল করুন, যোগফল[i] =যোগফল[i+1] এবং শেষে সর্বাধিক যোগফল ফেরত দিন যা যোগফল [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
