এই সমস্যায় একটি অ্যারে 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[]। incSeq[i]-তে arr[0...i] থেকে কঠোরভাবে বর্ধমান সাবসিকোয়েন্সের যোগফল, decSeq[i]-তে arr[i...n] থেকে কঠোরভাবে নিম্নমুখী সাবসিকোয়েন্সের যোগফল থাকবে। সর্বোচ্চ যোগফল হবে max(incSeq[i] + decSeq[i] - arr[i])।
উদাহরণ
#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 : "<আউটপুট
The Maximum Sum of Bi-tonic subsequence is : 33
