C++로 구현하는 최대 합 교대 부분 수열 알고리즘

개요

이 튜토리얼에서는 정수 배열이 주어졌을 때 최대 합 교대 부분 수열(maximum sum alternating subsequence)을 찾는 프로그램을 만들어 보겠습니다.

여기서 교대 부분 수열이란 처음에는 감소하고, 그다음에는 증가하고, 다시 감소하는 식으로 값의 증감이 번갈아 나타나는 수열을 의미합니다. 목표는 이러한 조건을 만족하는 부분 수열 중에서 원소들의 합이 가장 커지는 경우를 찾는 것입니다.

문제 이해하기

예를 들어 배열이 {8, 2, 3, 5, 7, 9, 10}라고 가정해 봅시다. 이때 가장 유리한 교대 부분 수열은 8, 7, 10입니다. 8에서 7로 감소한 뒤 7에서 10으로 증가하여 교대 조건을 만족하며, 그 합은 8 + 7 + 10 = 25로 가능한 경우 중 가장 큽니다.

알고리즘 접근 방식

이 문제는 다이나믹 프로그래밍(DP)으로 효과적으로 해결할 수 있습니다. 각 인덱스마다 두 가지 상태를 추적합니다.

• dec[i]: i번째 원소로 끝나고 마지막 단계가 감소인 교대 부분 수열의 최대 합
• inc[i]: i번째 원소로 끝나고 마지막 단계가 증가인 교대 부분 수열의 최대 합

배열을 순회하면서 현재 원소 i와 앞선 모든 원소 j를 비교합니다. arr[j] > arr[i]라면 감소 단계이므로 inc[j] + arr[i] 값으로 dec[i]를 갱신하고, 반대로 arr[j] < arr[i]라면 증가 단계이므로 dec[j] + arr[i] 값으로 inc[i]를 갱신합니다. 모든 탐색이 끝난 뒤 두 배열에 담긴 값들 중 최댓값이 곧 정답이 됩니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;

// 최대 합 교대 부분 수열의 합을 반환하는 함수
int maxAlternateSum(int arr[], int n) {
    if (n == 1) return arr[0];
    int dec[n];
    memset(dec, 0, sizeof(dec));
    int inc[n];
    memset(inc, 0, sizeof(inc));
    dec[0] = inc[0] = arr[0];
    int flag = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[i]) { dec[i] = max(dec[i], inc[j] + arr[i]); flag = 1; }
            else if (arr[j] < arr[i] && flag == 1) inc[i] = max(inc[i], dec[j] + arr[i]);
        }
    }
    int result = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (result < inc[i]) result = inc[i];
        if (result < dec[i]) result = dec[i];
    }
    return result;
}

int main() {
    int arr[] = {8, 2, 3, 5, 7, 9, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum sum = " << maxAlternateSum(arr, n) << endl;
    return 0;
}

출력 결과

Maximum sum = 25

복잡도 분석

위 구현은 이중 반복문을 사용하므로 시간 복잡도는 O(n²)이며, 감소·증가 상태를 저장하기 위한 두 개의 보조 배열을 사용하므로 공간 복잡도는 O(n)입니다. 배열의 길이가 길어질수록 실행 시간이 늘어나지만, 직관적인 DP 구조 덕분에 로직을 이해하고 응용하기에는 매우 적합한 접근 방식입니다.