C++ 中双调子序列的最大和
c++server side programmingprogramming
在这个问题中，我们给定一个数组 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] 中所有元素的和，严格递减。
最后，我们将返回 maxSum，即 (incSeq[i] + decSeq[i] - arr[i]) 中的最大值。
示例
程序用于说明我们的解决方案的措辞，
#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<<"双调子序列的最大和是 : "<<findMaxSumBiTonicSubSeq(arr, N);
return 0;
}
输出
双调子序列的最大和是 : 33
