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