C ++中的最大和双调子序列
在这个问题中，我们得到了一个数组arr[]。我们的任务是创建一个程序，以查找C++中最大的双调子序列。
双调子序列是一个特殊的序列，其元素先增加然后减少。
让我们举个例子来了解这个问题，
输入值
arr[] = {4, 2, 3, 7, 9, 6, 3, 5, 1}输出结果
33
说明
给出最大总和的双调子序列为{2，3，7，9，9，6，5，1}Sum=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