Longest Increasing Subsequence

• Time : $O(nlogn)$
• Space : $O(n)$

int Solution::lis(const vector<int> &A) {
    vector<int> dp;
    for(auto& a : A) {
        auto lb = lower_bound(begin(dp), end(dp), a);
        if(lb == end(dp)) dp.push_back(a);
        else *lb = a;
    }
    return dp.size();
}