Array算法之Longest increasing subsequence (LIS)

    今日在复习Longest increasing subsequence (LIS)的时候在wiki看到一个算法复杂度居然只有nlogn，但是wiki没有讲的太明白，然后又到万能的google一搜索，在princeton讲义pdf学到一个绝逼的算法，我和我的小伙伴都惊呆了。
    玩过接龙poker的人都知道接龙的greedy 算法吧，这算法就是用接龙greedy 算法进化而来。
greedy 算法就是把牌放在最左边并且符合条件的pile
如果牌数字依次是 6, 3, 5, 10, 11, 2, 9, 14, 13, 7, 4, 8, 12
6    5    10    11    14
3    4     9      8     13
2           7             12
这么一看是不是觉得距离获得LIS 不远了，还有一个tricky的地方是在加入每一个牌的时候要保留一个指向前面一个pile最顶端牌的指针，如图：

这样可以顺指针找到lis了。
在找leftmost pile的时候用binary search可以把复杂度降低到nlogn