title: How does algorithm for Longest increasing subsequence [O(nlogn)] work?
body: <p>I found algorithm mentioned in <a href="http://comscigate.com/Books/contests/icpc.pdf" rel="nofollow">The Hitchhiker’s Guide to the Programming Contests</a> (note: this implementation assumes there are no duplicates in the list):</p>
  
  <pre><code>set&lt;int&gt; st;
  set&lt;int&gt;::iterator it;
  st.clear();
  
  for(i=0; i&lt;n; i++) {
  
    st.insert(array[i]); it=st.find(array[i]);
  
    it++; if(it!=st.end()) st.erase(it);
  }
  
  cout&lt;&lt;st.size()&lt;&lt;endl;
  </code></pre>
  
  <p>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. </p>
  
  <p>Can anyone help me gain insight as to why this algorithm works correctly?</p>