C++での最大合計バイトニックサブシーケンス

この問題では、配列arr[]が与えられます。私たちのタスクは、C++で最大合計のBitonicサブシーケンスを見つけるプログラムを作成することです。

バイトニック サブシーケンスは、要素が最初に増加し、次に減少する特別なシーケンスです。

問題を理解するために例を見てみましょう

入力

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

ソリューションアプローチ

最大合計ビットニックサブシーケンスを見つけるために、2つの配列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<<"The Maximum Sum of Bi-tonic subsequence is : "<<findMaxSumBiTonicSubSeq(arr, N);
   return 0;
}

出力

The Maximum Sum of Bi-tonic subsequence is : 33