C++로 구현하는 최대 합 감소 부분 수열(MSDS) 알고리즘

이 문제에서는 N개의 정수로 이루어진 배열 arr[]가 주어지며, 우리의 목표는 C++를 이용해 최대 합 감소 부분 수열(Maximum Sum Decreasing Subsequence)을 찾는 것입니다.

문제 설명

배열에서 원소들을 선택해 엄격하게 감소하는(각 원소가 앞선 원소보다 작은) 부분 수열을 만들 때, 그 합이 최대가 되는 경우를 구해야 합니다.

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

입력

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

출력

17

설명

합이 최대가 되는 감소 부분 수열은 {10, 5, 2}이며, 그 합은 10 + 5 + 2 = 17입니다.

해결 접근 방법

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 인덱스 i까지 고려했을 때의 최대 합을 저장하는 maxSum[] 배열을 생성하고, 아래 공식을 이용해 배열의 값을 갱신합니다.

maxSum[i] = arr[i] + max(maxSum[0 … i-1])

즉, 현재 원소 arr[i]보다 큰 이전 원소들 중에서 maxSum 값이 가장 큰 경우에 현재 원소를 더해 maxSum[i]에 저장합니다. 최종적으로 maxSum[] 배열 전체에서 가장 큰 값이 곧 정답이 됩니다.

이 알고리즘의 시간 복잡도는 두 개의 중첩 반복문 때문에 O(N²)이며, 추가 배열 하나만 사용하므로 공간 복잡도 역시 O(N)입니다.

예제

다음 프로그램은 위 해결 방법의 동작 과정을 보여줍니다.

#include <iostream>
using namespace std;
int findMaxSumDecSubSeq(int arr[], int N){
    int maximumSum = 0;
    int maxSum[N];
    for (int i = 0; i < N; i++)
        maxSum[i] = arr[i];
    for (int i = 1; i < N; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] < arr[j] && maxSum[i] < maxSum[j] + arr[i])
            maxSum[i] = maxSum[j] + arr[i];
    for (int i = 0; i < N; i++)
            if (maximumSum < maxSum[i])
                maximumSum = maxSum[i];
    return maximumSum;
}
int main(){
    int arr[] = { 5, 4, 100, 3, 2, 101, 1 };
    int N= sizeof(arr) / sizeof(arr[0]);
    cout<<"The maximum sum of decreasing subsequence is "<<findMaxSumDecSubSeq(arr, N);
    return 0;
}

출력

The maximum sum of decreasing subsequence is 106

위 예제에서 {100, 3, 2, 1}이라는 감소 부분 수열의 합이 106으로 가장 크기 때문에, 프로그램은 106을 출력합니다.