최대 부분 수열 직접 구하기(LIS)

http://jaimemin.tistory.com/317?category=985009에서는 LIS의 길이만 구했는데 이번에는 직접 최대 부분 수열까지 구해보는 코드입니다.

/*

최대 증가 부분 수열을 실제로 계산하기

*/

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

int length; //수열 길이

int cache[101], S[100], choices[101];

//S[start]에서 시작하는 증가 부분 수열 중 최대 길이 반환

int LIS(int start)

{

        int &result = cache[start + 1];

        if (result != -1)

               return result;

        result = 0;

        int bestNext = -1;

        for (int next = start + 1; next < length; next++)

               if (start == -1 || S[start] < S[next]) //처음 index이거나 전보다 더 클 경우에만

               {

                       int candidate = LIS(next) + 1;

                       if (candidate > result)

                       {

                              result = candidate;

                              bestNext = next;

                       }

               }

        choices[start + 1] = bestNext;

        return result;

}

 

//S[start]에서 시작하는 LIS를 seq에 저장

void reconstruct(int start, vector<int> &seq)

{

        if (start != -1)

               seq.push_back(S[start]);

        int next = choices[start + 1];

        if (next != -1)

               reconstruct(next, seq);

}

 

int main(void)

{

        cout << "수열의 길이: ";

        cin >> length;

       

        cout << "수열 입력" << endl;

        for (int i = 0; i < length; i++)

               cin >> S[i];

        memset(cache, -1, sizeof(cache));

        memset(choices, -1, sizeof(choices));

        cout << "최대 증가 부분 수열의 길이: " << LIS(-1) << endl;

        vector<int> seq;

        reconstruct(-1, seq);

        cout << "최대 증가 부분 수열: ";

        for (int i = 0; i < seq.size(); i++)

               cout << seq[i] << " ";

        cout << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략