LIS (Longest Increasing Subsequence)

LIS 구현

 

1. lower bound 사용하여,

2. 

새로운 값 x가 기존 lower bound 배열의 가장 큰 값보다 크면 뒤에 추가

기존 lower bound 배열에서  x보다 같거나 큰 값 중 첫 번째를 찾아 업데이트 해준다.

즉 F, F, ... F, T, .. T 인 분포에서 x <= v[mid] 인 T의 첫 번째를 찾는 것.

 x <= v[mid] 가 아니면 lo = mid, 맞다면 hi = mid

 

https://www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3

위 문제는 LIS의 길이만 구하는 문제이다.

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<unordered_map>
#include<map>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#define INF 1e9
using namespace std;
using lld = long long int;
using pii = pair<int, int>;
 
 
int n;
int a[1000001];
 
int lowerbound(const vector<int>& v, int x) {
    int m = v.size();
    int lo = -1, hi = m;
    while(lo+1 < hi) {
        int mid = (lo + hi) / 2;
        if(!(x<=v[mid])) lo = mid;
        else hi = mid;
    }
    return hi;
}
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> a[i];
    }
    
    vector<int> v;
    v.push_back(a[0]);
    int pos = 0;
    
    for(int i=1; i<n; i++) {
        if(a[i] > v[pos]) {
            v.push_back(a[i]);
            pos++;
        }
        else {
            int idx = lowerbound(v, a[i]);
            v[idx] = a[i];
        }
    }
    
    cout << pos + 1 << "\n";
    
    return 0;
}
 
 
 

 

길이 뿐만 아니라 LIS의 실제 수열을 구하려면 

위 구현에 추가적인 값들을 저장한 후에 스택을 이용해 구할 수 있다.

방법과 풀이는 기회가 된다면 다음에.

https://www.acmicpc.net/problem/14003