longestIncreasingSubsequence.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestIncreasingSubsequence(const vector<int> &v) {
    vector<int> dp(v.size(), INT_MAX);
    for (int n : v ) {
        *lower_bound(dp.begin(), dp.end(), n) = n;
    }
    return lower_bound(dp.begin(), dp.end(), INT_MAX) - dp.begin();
}

int main(int argc, char *argv[]) {
    vector<int> v = {5, 1, 3, 2, 4};

    cout << longestIncreasingSubsequence(v) << endl;
    return 0;
}