LIS (하, p. 230)

LIS(Longest Increasing Subsequence) 문제는 vector와 binary search를 이용해서 $O(NlogN)$에 풀 수 있다.

소요 시간: 5분

1. $O(NlogN)$ 풀이 방법 (binary search)#

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        int n; cin >> n;
        for(int i=0; i<n; i++) {
            int x; cin >> x;
            if(v.empty()) v.push_back(x);
            else {
                if(v.back() < x) v.push_back(x);
                else {
                    auto it = lower_bound(v.begin(), v.end(), x);
                    *it = x;
                }
            }
        }
        printf("%lu\n", v.size());
        v.clear();
    }
    return 0;
}

2. $O(N^2)$ 풀이 방법 (DP)#

#include <bits/stdc++.h>
using namespace std;
int v[501];
int dp[501];
int f(int x) {
    if(x==0) return 1;
    if(dp[x]) return dp[x];

    int & ret = dp[x];
    ret=1;
    for(int i=0; i<x; i++) {
        if(v[i]<v[x]) ret = max(ret, f(i)+1);
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        int n; cin >> n;
        for(int i=0; i<n; i++) {
            cin >> v[i];
        }
        memset(dp, 0, sizeof(dp));

        int mx=0;
        for(int i=0; i<n; i++) {
            mx = max(mx, f(i));
        }
        printf("%d\n", mx);
    }
    return 0;
}