问题描述

在计算机科学中，最长递增子序列(longest increasing subsequence,简称LIS)问题是指在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能大。注意：最长递增子序列中的元素在原序列中不一定是连续的。 解决最长递增子序列问题的算法最低要求O(nlogn)。

---

问题举例

对于以下的原始序列 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

解决思想

令a[0…n-1]为输入数组，$lis_[i]$是索引在i处结束的LIS的长度，使得a[i]是LIS的最后一个元素。 然后，用递归法可以写出$L_{i}$：

• $L_{i}=1+max_{ \lparen L_{j} \rparen } \quad \lparen 0 < j<i\quad and\quad a[j]<a[i] \rparen$

• $L_{1}=1$

为了找出所给数组的LIS，我们给出max(L(i)) 即可(0<i<n)。 这里，因为可以使用子问题的解来解决主要问题，因此我们可以看到LIS问题具有最优子结构的属性。

---

下面给出LIS的递归实现

LIS 递归版

---

递归难免会出现重复子问题，一般，我们会用递推代替递归，事实证明，递推的效率高于递归。
下面给出LIS的递推版本

LIS no recursive