এই সমস্যায়, আমাদের একটি অ্যারে দেওয়া হয়েছে arr[]। আমাদের কাজ হল C++-এ সর্বাধিক যোগফল দ্বি-টনিক অনুসৃতি খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।
বাই-টনিক পরবর্তী ক্রম হল একটি বিশেষ ক্রম যার উপাদানগুলি প্রথমে বৃদ্ধি পায় এবং তারপর হ্রাস পায়৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {4, 2, 3, 7, 9, 6, 3, 5, 1} আউটপুট
33
ব্যাখ্যা
দ্বি-টনিক অনুসারী যা বৃহত্তম যোগফল দেয় তা হল {2, 3, 7, 9, 6, 5, 1} যোগফল =2 + 3 + 7 + 9 + 6 + 5 + 1 =33
সমাধান পদ্ধতি
সর্বাধিক যোগফল বিটোনিক অনুক্রমের জন্য, আমরা দুটি অ্যারে তৈরি করব, incSeq[] এবং decSeq[] এমনভাবে যাতে একটি উপাদান i সূচকে, incSeq[i]-এ arr[0…i] থেকে কঠোরভাবে সমস্ত উপাদানের যোগফল থাকে। বৃদ্ধি এবং decSeq[i]-এ arr[i…n] থেকে কঠোরভাবে হ্রাস হওয়া সমস্ত উপাদানের যোগফল রয়েছে।
শেষে, আমরা (incSeq[i] + decSeq[i] - arr[i]) থেকে সর্বাধিক মান হিসাবে maxSum ফেরত দেব।
উদাহরণ
আমাদের সমাধানের শব্দের ব্যাখ্যা করার জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
int calcMaxVal(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxSumBiTonicSubSeq(int arr[], int N){
int maxSum = -1;
int incSeq[N], decSeq[N];
for (int i = 0; i < N; i++){
decSeq[i] = arr[i];
incSeq[i] = arr[i];
}
for (int i = 1; i < N; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && incSeq[i] < incSeq[j] + arr[i]) incSeq[i] = incSeq[j] + arr[i];
for (int i = N - 2; i >= 0; i--)
for (int j = N - 1; j > i; j--)
if (arr[i] > arr[j] && decSeq[i] < decSeq[j] + arr[i])
decSeq[i] = decSeq[j] + arr[i];
for (int i = 0; i < N; i++)
maxSum = calcMaxVal(maxSum, (decSeq[i] + incSeq[i] - arr[i]));
return maxSum;
}
int main(){
int arr[] = {4, 2, 3, 7, 9, 6, 3, 5, 1};
int N = sizeof(arr) / sizeof(arr[0]);
cout<<"The Maximum Sum of Bi-tonic subsequence is : "<<findMaxSumBiTonicSubSeq(arr, N);
return 0;
} আউটপুট
The Maximum Sum of Bi-tonic subsequence is : 33
