5.最长上升子序列nlogn

最长上升子序列问题是指在一个给定的数列中，找到一个最长的子序列使得这个子序列中的元素是严格递增的。最长上升子序列问题可以通过动态规划来解决，但是其时间复杂度为 O(n^2)。为了降低时间复杂度，可以使用一种叫做“Patience Sorting”的方法，其时间复杂度为 O(nlogn)。

Patience Sorting方法的基本思想是，将原始序列中的每个元素尽可能地放到堆栈中（规则：新元素插入最左边的堆栈，如果无法插入则新建一个堆栈），这样得到的堆栈数量即为最长上升子序列的长度。由于每个元素只会被放入一个堆栈中，因此堆栈数量不会超过n，所以时间复杂度为O(nlogn)。