The Longest Increasing Subsequence problem

The Longest Increasing Subsequence problem can be solved by these methods:

1) Sort the sequence L into L_sorted, then find LCS(L, L_sorted). Since sort takes O(NlogN) time and LCS takes O(N^2) time, total it takes O(N^2) time.
2) There is a DP method [2]. It's O(N^2) and can be improved to O(NlogN) by using binary search.
3) Find the longest path in a directed acyclic graph. The source provides no detail on this solution. But it should be like building a tree with internal links (a DAG). It won't be easy.
4) Patience sort [3]. This is a card game and easy to understand by taking a deck of cards to try out oneself. Similar to the DP method, this is also O(N^2) and can be improved to O(NlogN) by using binary search. I prefer this method, since it's easy to find both the length and one of the LIS sequences.

Patience sort is an interesting sort [4]. This is one case where greedy strategy works optimally. Here are some excerpts from [4] about the history of patience sort:

The name "patience sorting" comes from Mallows (1973), who credits A.S.C. Ross for its invention for the motivation of sorting a deck of cards. Mallow's analysis was done in 1960 but not published until a long time later. Robert Floyd discovered this
independently and exchanged idea on it with Donald Knuth in private letters. Hammersley (1972) independently recognized its use as an algorithm for computing the length of LIS.

A related problem of LIS is LCIS: Longest Continuous Increasing Subsequence. This is much easier. A one-pass traversal of the sequence will do. we just keep 2 variables: the length of the current LCIS, and the ending location of it. At the end we know both the length and the location.

[1] http://en.wikipedia.org/wiki/Longest_increasing_subsequence
[2] http://blog.programfan.com/article.asp?id=13086
[3] http://en.wikipedia.org/wiki/Patience_sort
[4] Longest Increasing Subsequences: From Patience Sorting to the Baik-Dieft-Johansson Theorem. Caroline Gates, D. Aldous, Bull. Amer. Math. Soc., 36:413-32 (1999)