The O(NLog(N)) Approach To Find Longest Increasing Sub sequence
Let us maintain an array where the ith element is the smallest possible number with which a i sized sub sequence can end.
On purpose I am avoiding further details as the top voted answer already explains it, but this technique eventually leads to a neat implementation using the set data structure (at least in c++).
Here is the implementation in c++ (assuming strictly increasing longest sub sequence size is required)
#include <bits/stdc++.h> // gcc supported header to include (almost) everything
using namespace std;
typedef long long ll;
int main()
{
ll n;
cin >> n;
ll arr[n];
set<ll> S;
for(ll i=0; i<n; i++)
{
cin >> arr[i];
auto it = S.lower_bound(arr[i]);
if(it != S.end())
S.erase(it);
S.insert(arr[i]);
}
cout << S.size() << endl; // Size of the set is the required answer
return 0;
}