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):
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? asked 18 May '16, 09:15

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? let's take the example  1 3 4 2 5 And voilà,we just got our solution :D. Print the size of the set and that is the correct answer. answered 18 May '16, 13:06
