최대 합 증가 부분 수열(MSIS) 알고리즘

최대 합 증가 부분 수열(Maximum Sum Increasing Subsequence)은 주어진 정수 목록에서 만들 수 있는 부분 수열 중, 모든 원소가 오름차순으로 배치되어 있으면서 그 합이 가장 큰 부분 수열을 의미합니다.

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 각 인덱스 i에 대해 'arr[i]로 끝나는 최대 합 증가 부분 수열'을 저장하는 배열 L을 사용하며, 여기서 L[i]는 array[i]로 끝나는 최대 합 증가 부분 수열이 됩니다.

입력 및 출력

입력:
정수 수열 {3, 2, 6, 4, 5, 1}
출력:
합이 최대가 되는 증가 부분 수열 {3, 4, 5}

예시에서 {3, 6}의 합은 9이지만, {3, 4, 5}의 합은 12로 더 큽니다. 따라서 이 경우 정답은 {3, 4, 5}가 됩니다.

알고리즘

함수 maxSumSubSeq(array, n)은 다음과 같이 동작합니다.

입력: 숫자로 이루어진 수열, 원소의 개수

출력: 합이 최대인 증가 부분 수열

Begin
    define array of arrays named subSeqLen of size n.
    add arr[0] into the subSeqLen
    for i in range (1 to n-1), do
        for j in range (0 to i-1), do
            if arr[i] > arr[j] and sum of subSeqLen [i] < sum of subSeqLen [j], then
                subSeqLen[i] := subSeqLen[j]
        done
    done

    add arr[i] into subSeqLen[i]
    res := subSeqLen[0]
            
    for all values of subSeqLen, do
        if sum of subSeqLen[i] > sum of subSeqLen[res], then
            res := subSeqLen[i]
    done

    print the values of res.

End

알고리즘 단계별 설명

1. 크기가 n인 2차원 배열(벡터의 벡터) subSeqLen을 선언하고, 첫 번째 원소 arr[0]을 subSeqLen[0]에 추가합니다.

2. i를 1부터 n-1까지 반복하면서, 각 i에 대해 j를 0부터 i-1까지 탐색합니다. 이때 arr[i] > arr[j]이고 subSeqLen[i]의 합이 subSeqLen[j]의 합보다 작다면, subSeqLen[i]에 subSeqLen[j]를 복사합니다.

3. 내부 반복이 종료되면 subSeqLen[i]에 arr[i]를 추가하여, arr[i]로 끝나는 증가 부분 수열을 완성합니다.

4. 마지막으로 모든 subSeqLen 값 중 합이 가장 큰 것을 res로 선택한 뒤 출력합니다.

C++ 구현 예제

#include <iostream>
#include <vector>
using namespace std;
 
int findAllSum(vector<int> arr) {     //find sum of all vector elements
    int sum = 0;

    for(int i = 0; i<arr.size(); i++) {
        sum += arr[i];
    }

    return sum;
}
 
void maxSumSubSeq(int arr[], int n) {
    vector <vector<int> > subSeqLen(n);     //max sum increasing subsequence ending with arr[i]
    subSeqLen[0].push_back(arr[0]);

    for (int i = 1; i < n; i++) {         //from index 1 to all
        for (int j = 0; j < i; j++) {     //for all j, j<i
            
            if ((arr[i] > arr[j]) && (findAllSum(subSeqLen[i]) < findAllSum(subSeqLen[j])))
                subSeqLen[i] = subSeqLen[j];
        }
        
        subSeqLen[i].push_back(arr[i]);     //sub Sequence ends with arr[i]
    }

    vector<int> res = subSeqLen[0];

    for(int i = 0; i<subSeqLen.size(); i++) {
        if (findAllSum(subSeqLen[i]) > findAllSum(res))
            res = subSeqLen[i];
    }

    for(int i = 0; i<res.size(); i++)
        cout << res[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = { 3, 2, 6, 4, 5, 1 };
    int n = 6;
    cout << "The Maximum Sum Subsequence is: ";
    maxSumSubSeq(arr, n);
}

실행 결과

The Maximum Sum Subsequence is: 3 4 5

시간 복잡도