在这个问题中,我们得到了一个数组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