इस समस्या में, हमें एक सरणी 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[] इस तरह बनाएंगे कि इंडेक्स पर एक तत्व i के लिए, incSeq[i] में arr[0...i] से सख्ती से बढ़ते सभी तत्वों का योग हो और decSeq[i] में arr[i...n] से सख्ती से घटते सभी तत्वों का योग हो।
अंत में, हम (incSeq[i] + decSeq[i] - arr[i]) से अधिकतम मान के रूप में maxSum वापस करेंगे।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#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 : "<<findMaxSumBiTonicSubSeq(arr, N);
return 0;
}
आउटपुट
The Maximum Sum of Bi-tonic subsequence is : 33