Longest increasing subsequence implementation in C++

LIS.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<ll> LIS(vector<ll> &a) {
    vector<ll> dp(1);              // dp[i] = ending of LIS with length i
    vector<ll> pos(1);             // pos[i] = LIS with length i last element index in a
    unordered_map<ll, ll> parent;  // parent index of a[i] in LIS, -1 mean first element
    for (ll i = 0; i < a.size(); i++) {
        ll LIS_size = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();
        parent[a[i]] = (LIS_size == 1 ? -1 : pos[LIS_size - 1]);
        if (LIS_size == dp.size()) {  // a[i] is the largest element => longer LIS
            dp.push_back(a[i]);
            pos.push_back(i);
        } else {  // Make LIS with length LIS_size ending smaller
            dp[LIS_size] = a[i];
            pos[LIS_size] = i;
        }
    }
    // Reconstruct LIS only work if all element in a is unique
    // If you only want LIS size, return dp.size() - 1
    vector<ll> ans = {dp.back()};
    while (parent[ans.back()] != -1) {
        ans.push_back(a[parent[ans.back()]]);
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    for (ll &i : a) cin >> i;
    vector<ll> lis = LIS(a);
    for (ll i : lis) cout << i << ' ';
}