最长递增子序列（Longest Increasing Subsequence）

最长上升子序列（Longest Increasing Subsequence，LIS），在计算机科学上是指一个序列中最长的单调递增的子序列。

给定一个长度为 N 的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为 5 的数组{5， 6， 1， 2， 8}，则其最长的单调递增子序列为 {5，6，8}，长度为 3。

该方法的时间复杂度为 。

下面我们用一个实例来分析一下动态规划求解 LIS 的整个过程。假设数组 A 的内容为 {5, 6, 1, 2, 8}。

1、第一个元素直接设置 LIS 长度为 1 即可。如下图所示。

2、第二个元素 6 大于前面所有元素进行比较。55，则 LIS 的长度可能为 LIS[0]+1 = 2；取最大值，LIS[4]=3 。如下图所示。

设长度为 N 的数组为 {a0，a1, a2, ..., an-1)，则假定以 aj 结尾的数组序列的最长递增子序列长度为 LIS(j)，则 LIS(j) = {max(LIS(i))+1, iLIS[0]，构成递增，将数字 6 加入到 LIS 数组中，即 LIS[1]=6，表示长度为 2 的 LIS 数组的末尾是 6。如下图所示。

3、第三个元素为 1，1