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*);

it=st.find(array*);

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?