LIS(Longest Increasing Subsequence)

원소 $N$개인 배열의 일부 원소를 골라 증가하는 부분 수열을 이룰 때, 가장 긴 증가하는 부분 수열의 길이를 구하는 코드를 작성하라

LIS 알고리즘의 구현

---

만약 {1,2,4,5,3,4,5}인 $a$배열이 주어졌을 때 {1,2,3,4,5}의 부분 수열의 길이가 5인 수열이 LIS의 길이가 된다.

DP를 이용하면 쉽게 구현할 수 있다.

• $dp[i]$ : $i$번째 원소까지 부분 수열을 체크했을 때 최장 길이

vector<int> a(len);
int dp[len];

int LIS() {
    dp[0]=0;
    int lis=0;
    for(int i=0;i<len;i++) {
        dp[i]=1; // 기본 길이
        for(int j=0;j<i;j++) {
            if(a[i]>a[j] && dp[j]+1>dp[i]) {
                dp[i]=dp[j]+1;
            }
        }
        lis=max(lis,dp[i]);
    }
    return lis;
}

그러나 위의 코드는 이중 for문 때문에 $O(N^2)$의 시간 복잡도를 가지게 된다.

그래서 이분탐색을 통해 시간 복잡도를 줄이고자 한다.

이분탐색을 통해 LIS를 유지하기 위한 최적의 위치에 원소를 삽입하는 방법을 사용할 수 있다.

vector<int> a(len);
int lis() {
    vector<int> v;
    v.push_back(-INF); // 최소 길이는 1로 맞추기 위해
    for(auto it : a) {
        if(v.back()<it) { // 증가하는 수라면 뒤에 삽입
            v.push_back(it);
        }
        else { // 증가하지 않는 수라면 lower_bound로 삽입시킬 위치를 찾고 치환한다
            auto it=lower_bound(v.begin(),v.end(),it);
            *it=x;
        }
    }
    return v.size();
}

위의 코드는 $a$배열의 크기 $N$을 도는 for문이 있고 그 안에 $v$를 이분 탐색하는 코드가 존재한다. 따라서 $O(NlogN)$의 시간 복잡도를 가진다.