C++로 구현하는 최대 합 바이토닉(Bi-tonic) 부분 수열

이 문제에서는 배열 arr[]가 주어지며, C++을 사용해 이 배열에서 최대 합 바이토닉(Bi-tonic) 부분 수열을 찾는 프로그램을 작성하는 것이 목표입니다.

바이토닉 부분 수열이란 원소들이 먼저 증가하다가 이후 감소하는 형태를 가지는 특수한 수열을 말합니다.

문제 이해를 위한 예시

입력

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

해결 접근 방법

최대 합 바이토닉 부분 수열을 찾기 위해 두 개의 배열 incSeq[]와 decSeq[]를 생성합니다.

• incSeq[i]: arr[0…i] 범위에서 인덱스 i의 원소로 끝나는, 엄격하게 증가하는 부분 수열의 최대 합
• decSeq[i]: arr[i…n] 범위에서 인덱스 i의 원소로 시작하는, 엄격하게 감소하는 부분 수열의 최대 합

모든 계산이 끝난 후, 각 인덱스 i에 대해 (incSeq[i] + decSeq[i] − arr[i]) 값을 구하고 그중 최댓값을 maxSum으로 반환합니다. 여기서 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

이 알고리즘은 동적 계획법(DP)을 기반으로 하며, 시간 복잡도는 O(N²), 공간 복잡도는 O(N)입니다. 배열의 길이가 N일 때 증가 수열과 감소 수열을 각각 한 번씩 순회하므로, 중간 규모의 입력까지 효율적으로 처리할 수 있습니다.