How this algorithm for LIS works ?

general
1

This is the O(n*lg(n)) solution for Longest Increasing subsequence taken from The Hitchhiker’s Guide to the Programming Contests (note: this implementation assumes there are no duplicates in the list):

enter code here
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;

I am not able to understand why this algorithm works? Can anybody help me out?

2

See basically,in set all the elements will be sorted(increasing order) and no duplicates will be allowed. Now we should start with an example,shall we?
basically we’re going to check that after insertion whether the element is inserted in the last position or not. If yes,then we can continue with this number,else we’ll erase it.

let’s take the example - 1 3 4 2 5
For the iteration 1: set: 1(1 in Last)
For the iteration 2: set: 1 3(3 in Last)
For the iteration 3: set: 1 3 4 (4 in last)
For the iteration 4: set: 1 2 3 4(2 in 2nd,so we’ll remove 2,so the new set 1 3 4)
For the iteration 5: set: 1 3 4 5(5 in last)

And voilà,we just got our solution :D. Print the size of the set and that is the correct answer.
Feel free to ask me,if you’ve any doubts. :slight_smile: