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