इस समस्या में, हमें एक सरणी 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