最长递增子序列(Longest Increasing Subsequence, LIS) 是非常经典的一个算法问题。
在计算机科学中，最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。许多与数学、算法、随机矩阵理论、表示论相关的研究都会涉及最长递增子序列。
例如，对于以下的原始序列：
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15最长递增子序列为
0, 2, 6, 9, 11, 15值得注意的是原始序列的最长递增子序列并不一定唯一，对于该原始序列，实际上还有以下三个最长递增子序列
0, 4, 6, 9, 11, 15
0, 4, 6, 9, 13, 15
0, 2, 6, 9, 13, 15【以上摘自 wikipedia】
动态规划求解
动态规划所使用的时间复杂度为 $O(n^2)$
令当前元素为 x，对于之前的每个比其小的元素 y，以 x 结尾的最长递增子序列 $\text{LIS}_x$ 都有可能是在以 y 结尾的 $\text{LIS}_y$ 基础上将 x 执行 append，即 $\text{LIS}_x = \text{LIS}_y.\text{append}(x)$。
若要使 LISx 最长，就必须找到一个最长的 $\text{LIS}_y$。假设状态 $\text{LEN}_x$ 表示 $\text{LIS}_x$ 的最大长度，那么有
$$ \text{LEN}x = \max(\text{LEN}{y_i}) + 1, \quad y_i < x $$
转换成代码风格就是（以 C++ 代码为例）：
1for (int i = 1; i < n; i++) {
2 int maxLength = 0;
3 for (int j = 0; j < i; j++) {
4 maxLength = max(maxLength, len[y]);
5 }
6 len[x] = maxLength + 1;
7}
最后遍历所有元素结尾的 LEN，找到最大的那个即可。
缺点
动态规划方法的一个缺点在于——状态的冗余检查。极端情况下，如果一个序列严格递增，比如 1, 2, 3, 4, 5, 6 ，那么其 LIS 就是本身，但在遍历到元素 3 的时候，其会把 $\text{LIS}_1$ 与 $\text{LIS}_2$ 都检查一遍。事实上， $\text{LIS}_2$ 包含了 $\text{LIS}_1$，对后者的检查是完全没有必要的。
更别说后面的 4, 5, 6 了。
需要找到一个方法来消除该冗余，最好是遍历到某一元素
x时，我们已经知道 $\text{LIS}_x$ 与前面所有元素的关系。
nlogn
换个思路，将所要存储的状态修改为「长度为 k 的 LIS 的最后一个元素」，看看事情是否有所转机？
以序列 5, 1, 4, 2, 8, 7, 9, 0, 3, 6 为例：
i = 0时，lastElementWithLength[1]为 5，这很显然；lastElementWithLength: 5
i = 1时，1 比 5 小，为了使后续元素更容易得到 append，将lastElementWithLength[1]改为 3；lastElementWithLength: 1
i = 2时，4 比 1 大，可以作为递增子序列1, 4的最后一个元素，所以令lastElementWithLength[2]为 4；lastElementWithLength: 1, 4
i = 3时，2 比 4 小，但比 1 大，根据前面的理论，将lastElementWithLength[2]改为 2。当然这并不是说前面的4就消失了，它依然可以作为递增子序列1, 4的一部分，但是一旦后续出现数字3，它会更倾向于比自己小并且长度不低的2；lastElementWithLength: 1, 2
以此类推，我们最终可以得到这样一个 lastElementWithLength 数组：
| 1 | 2 | 3 | 4 |
|---|---|---|---|
| 0 | 2 | 3 | 6 |
可以得到 LIS 的长度为 4，并且以 6 结尾。
LIS 为
1, 2, 3, 6
我们并不用在意之前有什么，只需要知道当前的元素必须被尽可能长的子序列 append 就可以了。对于那些末尾元素比自己还小的，肯定能进行 append 操作，而那些末尾元素比自身大的，则有可能取而代之，很典型的就是上面 i=3 时的情况。
事实上，在 lastElementWithLength 数组中，有且仅有第一个比自己大的那个元素 first 能进行取代，毕竟前面的那些再大也不会超过自身，first 也是在前者的基础上加入的数组，尽管取代了，也比之前的所有元素大。而后面的那些更大的元素，也必然是在 first 的基础上建立，其对应的递增子序列必然包含 first（或者更大的元素），一旦取代就会破坏 LIS 的规则。
所以问题又转变成了：在 lastElementWithLength 数组中找到第一个比自己大的元素。这不就二分法么？如果找不到，直接在末尾添加便是！
这样一来，遍历的过程中每个元素执行一次二分法，在最极端（也就是原始数组严格递增）的情况下也仅仅需要 $O(n\log n)$ 的时间复杂度，比起动态规划，开销大大降低。
应用
传送门：