Longest Increasing Subsequence - O( n*log(n) )

/**------------------------
    Author : NikolaP
    Compiler : C++
-------------------------*/

//{         Setup

    #include <bits/stdc++.h>
    using namespace std;

    typedef long long int ll;
    typedef long double ld;
    typedef vector<int> vi;

    const int inf = INT_MAX;
    const bool debug = 0;

//}


int lis(vi& v){
    int n = v.size();
    vi dp(n+1,inf);

    dp[0] = -inf;

    for(int i=0; i < n; ++i){
        int idx = upper_bound(dp.begin(), dp.end(),v[i]) - dp.begin();

        if(dp[idx-1] < v[i] and v[i] < dp[idx])
            dp[idx] = v[i];
    }

    int ans = 0;
    for(int i = 0; i <= n; ++i){
        if(dp[i] < inf) ans = i;
    }

    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(8);
    //cout << fixed;

    vi v = {1,2,3,4,5};
    cout << lis(v);
    return 0;
}