Longest Increasing Subsequence

Given an array of integers, find the length of the longest (strictly) increasing subsequence from the given array.

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

class Solution
{
public:
    //Function to find length of longest increasing subsequence.
    int longestSubsequence(int n, int a[])
    {
        vector<int> lcs;
        for(int i = 0; i < n; i++) {
            if(lcs.empty() or lcs.back() < a[i]) lcs.push_back(a[i]);
            else {
                auto it = lower_bound(begin(lcs), end(lcs), a[i]);
                *it = a[i];
            }
        }

        return lcs.size();
    }
};