The Longest Increasing Subsequence

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

int longestIncreasingSubsequence(vector<int> arr) {
    vector<int> lis;
    for(auto& a : arr) {
        if(lis.empty() or lis.back() < a) lis.push_back(a);
        else {
            auto lb = lower_bound(begin(lis), end(lis), a);
            *lb = a;
        }
    }
    
    return lis.size();
}