C++-এ সর্বোচ্চ যোগফল বি-টোনিক সাবঅ্যারে (Maximum Sum Bitonic Subarray)

এই সমস্যায় একটি অ্যারে 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[] তৈরি করব। incSubArr[i]-তে 0 থেকে i পর্যন্ত বর্ধমান সাবঅ্যারে, decSubArr[i]-তে i থেকে N-১ পর্যন্ত নিম্নমুখী সাবঅ্যারের যোগফল থাকবে। সর্বোচ্চ যোগফল = max(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 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
আউটপুট
The Maximum Sum of Bitonic Subarray is 30