LIS + 역추적

"[14003] 가장 긴 증가하는 부분 수열 5"를 베이스로 둔다.

dp로 O(N^2)에 풀 수 있는 문제이지만, 이분탐색으로 O(NlogN)에 동작하도록 만들 수 있고

다익스트라와 마찬가지로 '이전에 어디에서 왔는지'를 저장하면 최장 길이와 해당 수열도 구할 수 있다.

이분탐색은 lower_bound()로 간단하게 구현할 수 있고, iterator를 index처럼 사용하려면 begin()을 빼면 된다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

vector<ll> a;

ll n;

void lis(vector<ll>& ret) {

    vector<ll> v, path(n);

    for (ll i = 0; i < n; i++) {

        ll idx = lower_bound(v.begin(), v.end(), a[i]) - v.begin();

        path[i] = idx;

        if (v.begin() + idx == v.end())

            v.push_back(a[i]);

        else

            v[idx] = a[i];

    }

    ll S = v.size();

    for (ll i = n - 1; i >= 0 && S > 0; i--) {

        if (path[i] == S - 1) {

            S--;

            ret.push_back(a[i]);

        }

    }

    reverse(ret.begin(), ret.end());

    return;

}

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> n;

    a.resize(n);

    ll i;

    for (i = 0; i < n; i++) cin >> a[i];

    vector<ll> ans;

    lis(ans);

    cout << ans.size() << '\n';

    for (auto& i : ans) cout << i << ' ';

    return 0;

}

 

사실 코드 자체가 짧아서 템플릿화하는 의미가 크게 없다.

최적해를 추적하는 부분까지 구현했으나, 단순히 길이만 찾고 싶다면 코드가 정말 짧다.