Different algorithms for longest increasing subsequence
There is a $O(n \log \log n)$ time algorithm to solve the longest increasing subsequence problem. You may find this and the paper by Sergei Bespamyatnikh , Michael Segal helpful.