C++의 최대 합 Bi-tonic 하위 시퀀스

이 문제에서는 배열 arr[]이 제공됩니다. 우리의 임무는 C++에서 최대합 Bi-tonic 부분수열을 찾는 프로그램을 만드는 것입니다.

바이토닉 하위 시퀀스는 요소가 먼저 증가하고 감소하는 특수 시퀀스입니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력

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

출력

33

설명

가장 큰 합을 주는 Bi-tonic 부분수열은 {2, 3, 7, 9, 6, 5, 1}입니다. Sum =2 + 3 + 7 + 9 + 6 + 5 + 1 =33

솔루션 접근 방식

최대 합 비트 하위 시퀀스를 찾기 위해 인덱스의 요소 i에 대해 incSeq[i]가 엄격하게 arr[0… 증가하고 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