C++로 최대 합 비토닉 부분 배열 구하기

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

비토닉 부분 배열(Bitonic Subarray)이란 요소들이 먼저 엄격하게 증가하다가 특정 지점(정점)에 도달한 후 다시 엄격하게 감소하는 형태를 가진 특수한 부분 배열을 의미합니다.

예시를 통해 문제를 자세히 살펴보겠습니다.

입력

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

출력

30

설명

위 배열에서 비토닉 부분 배열은 [2, 3, 7, 9, 6, 3]입니다.
합계 = 2 + 3 + 7 + 9 + 6 + 3 = 30

해결 접근 방법

이 문제의 풀이 방식은 비토닉 부분 수열(bitonic subsequence) 문제와 유사합니다. 핵심 아이디어는 두 개의 보조 배열 incSubArr[]와 decSubArr[]를 생성하여 각각의 구간 합을 미리 계산해 두는 것입니다.

• incSubArr[i]: 인덱스 0부터 i까지 이어지는 증가 구간의 합을 저장합니다.
• decSubArr[i]: 인덱스 i부터 N-1까지 이어지는 감소 구간의 합을 저장합니다.

각 인덱스 i에서 (incSubArr[i] + decSubArr[i] - arr[i])를 계산하고, 그중 최대값이 곧 정답(maxSum)이 됩니다. 여기서 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

복잡도 분석

이 알고리즘은 배열을 세 번 순회하므로 시간 복잡도는 O(N)입니다. 또한 증가 구간과 감소 구간의 합을 저장하기 위해 두 개의 보조 배열을 사용하므로 공간 복잡도 역시 O(N)입니다.