C++での最大合計バイトニックサブアレイ

この問題では、配列arr[]が与えられます。私たちのタスクは、C++で最大の合計バイトニックサブアレイを見つけるプログラムを作成することです。

Bitonicサブアレイ は、要素が最初に厳密に増加し、特定のポイントに到達した後に厳密に減少する特別なサブ配列です。

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

入力

arr[] = {4, 2, 3, 7 ,9, 6, 3, 5, 1}

出力

30

説明

バイトニックサブアレイは[2、3、7、9、6、3]です。合計=2 + 3 + 7 + 9 + 6 + 3 =30

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

解決策は、ビットニック部分列問題の解決策と似ています。 2つの配列incSubArr[]とdecSubArr[]を作成します。これにより、ストアの増加および減少するサブ配列が作成されます。インデックスiで、incSubArr[i]はサブ配列が0からiに増加していることを検出します。そして、decSubArr [i]は、サブアレイがiからNに増加していることを検出します。

maxSumは、（incSubArr [i] + decSubArr [i] --arr [i]）として計算される最大値です。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int findMaxSumBiTonicSubArr(int arr[], int N){
   int incSubArr[N], decSubArr[N];
   int max_sum = -1;
   incSubArr[0] = arr[0];
   for (int i=1; i<N; i++)
      if (arr[i] > arr[i-1])
         incSubArr[i] = incSubArr[i-1] + arr[i];
      else
         incSubArr[i] = arr[i];
   decSubArr[N-1] = arr[N-1];
   for (int i= (N-2); i>=0; i--)
      if (arr[i] > arr[i+1])
         decSubArr[i] = decSubArr[i+1] + arr[i];
      else
         decSubArr[i] = arr[i];
   for (int i=0; i<N; i++)
      if(max_sum < (incSubArr[i] + decSubArr[i] - arr[i]))
max_sum = incSubArr[i] + decSubArr[i] - arr[i];
   return max_sum;
}
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 Bitonic Subarray is "<<findMaxSumBiTonicSubArr(arr, N);
   return 0;
}

出力

The Maximum Sum of Bitonic Subarray is 30