একটি সাব-সিকোয়েন্সের জন্য সর্বোচ্চ যোগফল যাতে C++ প্রোগ্রামের অ্যারেতে

এই সমস্যায়, আমাদের n আকারের একটি অ্যারে অ্যারে [] এবং একটি পূর্ণসংখ্যা k দেওয়া হয়েছে। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যাতে পরবর্তীতে সম্ভাব্য সর্বাধিক যোগফল খুঁজে পাওয়া যায় যাতে কোনো দুটি উপাদান দূরত্বে

সমস্যা বর্ণনা − আমাদের উপ-অনুক্রমের সর্বাধিক যোগফল খুঁজে বের করতে হবে যা উপাদানগুলিকে বিবেচনা করে যেগুলি একে অপরের থেকে k দূরত্ব।

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

ইনপুট

arr[] = {6, 2, 5, 1, 9, 11, 4} k = 2

আউটপুট

16

ব্যাখ্যা

All possible sub−sequences of elements that differ by k or more.
{6, 1, 4}, sum = 11
{2, 9}, sum = 11
{5, 11}, sum = 16
{1, 4}, sum = 5
...
maxSum = 16

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

সমস্যার একটি সমাধান হল ডায়নামিক প্রোগ্রামিং ব্যবহার করা। সমাধানের জন্য, আমরা অ্যারের বর্তমান উপাদান পর্যন্ত সর্বাধিক সম্ভাব্য যোগফল খুঁজে পাব। এবং এটিকে DP[i]-এ সংরক্ষণ করুন, এর জন্য আমরা সর্বাধিক সম্ভাব্য যোগফল খুঁজে পাব। i-th সূচকের জন্য, আমাদের পরীক্ষা করতে হবে যে বর্তমান সূচকের মান যোগ করলে সাব-সিকোয়েন্স যোগফল বাড়ে কি না।

if( DP[i − (k+1)] + arr[i] > DP[i − 1] )
−> DP[i] = DP[i − (k+1)] + arr[i]
otherwise DP[i] = DP[i−1]

ডায়নামিক অ্যারের সর্বোচ্চ উপাদান সর্বাধিক অনুসূচী দেয়।

অ্যালগরিদম

শুরু করুন −

maxSumSubSeq = −1, maxSumDP[n]

ধাপ 1 −

Initialize maxSumDP[0] = arr[0]

ধাপ 2 −

Loop for i −> 1 to n.

ধাপ 2.1৷ −

if i < k −> maxSumDP[i] = maximum of arr[i] or
maxSumDP[i− 1].

ধাপ 2.2৷ −

else, maxSumDP[i] = maximum of arr[i] or maxSumDP[i − (k + 1)] + arr[i].

ধাপ 3 −

Find the maximum value of all elements from maxSumDP and store
it to maxSumSubSeq.

পদক্ষেপ 4৷ −

Return maxSumSubSeq

উদাহরণ

আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,

#include <iostream>
using namespace std;
int retMaxVal(int a, int b){
   if(a > b)
   return a;
   return 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