এই সমস্যায়, আমাদের একটি অ্যারে দেওয়া হয়েছে arr[]। আমাদের কাজ হল C++ এ সর্বাধিক যোগফল বিটোনিক সাবয়ারে খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।
বিটোনিক সাবারে একটি বিশেষ সাবয়ারে যেখানে উপাদানটি প্রথমে কঠোরভাবে বৃদ্ধি পায় এবং তারপর একটি নির্দিষ্ট বিন্দুতে পৌঁছানোর পরে কঠোরভাবে হ্রাস পায়৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {4, 2, 3, 7 ,9, 6, 3, 5, 1} আউটপুট
30
ব্যাখ্যা
বিটোনিক সাবয়ারে হল [2, 3, 7, 9, 6, 3]। যোগফল =2 + 3 + 7 + 9 + 6 + 3 =30
সমাধান পদ্ধতি
সমাধানটি বিটোনিক পরবর্তী সমস্যাগুলির মতোই। আমরা incSubArr[] এবং decSubArr[] দুটি অ্যারে তৈরি করব। এটি স্টোর ক্রমবর্ধমান এবং হ্রাসকারী সাবয়ারে তৈরি করবে। ইনডেক্স i-এ, incSubArr[i] 0 থেকে i পর্যন্ত ক্রমবর্ধমান সাবঅ্যারে খুঁজে পাবে। এবং decSubArr[i] i থেকে N পর্যন্ত ক্রমবর্ধমান সাবারে খুঁজে পাবে।
maxSum হল সর্বাধিক মান হিসাবে গণনা করা হয় (incSubArr[i] + decSubArr[i] - arr[i])।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
int findMaxSumBiTonicSubArr(int arr[], int N){
int incSubArr[N], decSubArr[N];
int max_sum = -1;
incSubArr[0] = arr[0];
for (int i=1; i<N; i++)
if (arr[i] > arr[i-1])
incSubArr[i] = incSubArr[i-1] + arr[i];
else
incSubArr[i] = arr[i];
decSubArr[N-1] = arr[N-1];
for (int i= (N-2); i>=0; i--)
if (arr[i] > arr[i+1])
decSubArr[i] = decSubArr[i+1] + arr[i];
else
decSubArr[i] = arr[i];
for (int i=0; i<N; i++)
if(max_sum < (incSubArr[i] + decSubArr[i] - arr[i]))
max_sum = incSubArr[i] + decSubArr[i] - arr[i];
return max_sum;
}
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 Bitonic Subarray is "<<findMaxSumBiTonicSubArr(arr, N);
return 0;
} আউটপুট
The Maximum Sum of Bitonic Subarray is 30
