इस समस्या में, हमें एक ऐरे एरर [] दिया जाता है। हमारा काम 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 तक बढ़ते हुए उप-सरणी पाएंगे।
मैक्ससम अधिकतम मूल्य है जिसकी गणना (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