How does algorithm for Longest increasing subsequence [O(nlogn)] work?

Question

I found algorithm mentioned in The Hitchhiker’s Guide to the Programming Contests (note: this implementation assumes there are no duplicates in the list):

set<int> st;
set<int>::iterator it;
st.clear();

for(i=0; i<n; i++) {

  st.insert(array[i]); it=st.find(array[i]);

  it++; if(it!=st.end()) st.erase(it);
}

cout<<st.size()<<endl;

It's an algorithm to find longest increasing subsequence in O(NlogN). If I try to work it with few test cases, it seems to work. But I still couldn't figure out its correctness logic. Also, it doesn't look so intuitive to me.

Can anyone help me gain insight as to why this algorithm works correctly?

Answer 1

How to determine the longest increasing subsequence using dynamic programming?

Please read my explanation there first. If it is still not clear, read the following:

The algorithm keeps the lowest possible ending number for LIS of every length. By keeping the lowest numbers, you can extend the LIS in a maximal way. I know this is not a proof, but maybe it will be intuitive for you.