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.

Answer 2

Statement: For each i, length of current set is equal to the length of the largest increasing subsequence.

Proof: Lets use the method of induction:

Base case : Trivially true.

Induction hypothesis: Suppose we have processed i-1 elements and the length of the set is LIS[i-1], i.e the length of the LIS possible with first i-1 elements.

Induction step: Inserting an element array[i] in the set will result in two cases.

1. A[i] >= set.last() : In this case A[i] will be the last element in the set and hence the LIS[i] = LIS[i-1]+1.

2. A[i] < set.last() : In this case we insert A[i] into the set and knock off element just greater than A[i] in the sorted order. LIS[i] = LIS[i-1] + 1(adding A[i]) - 1 (removing one elem > A[i]). Which is true. Hence proved.

To explain the big picture. Inserting A[i] into the set will either add to the LIS[i-1] or will create a LIS of its own, which will be the elements from 0th position to the position of the ith element.