LIS即求给入序列中的最长升序子序列，是学习DP的入门经典。
在此我给出两种算法，由浅至深。只求子序列长度。
算法一：
数据定义：
a[] : 输入序列
d[] : 保存最长升序子序列的子问题。
d[i] 表示以a[i]结尾的最长子序列的长度。
d[]初始化为1。因为子序列最短也是1。
n : a 和 d的长度
状态转移方程：（DP和递推虽然很像，但有概念上的差异）
d[t] = Max{d[i] + 1} (a[t] > a[i] && 0 <= i < t)
算法分析：
求解一个d[t]需要一个循环取最大值，时间复杂度为O(n)，所以总的时间复杂度是 O(n^2)。
程序使用双重循环构造d数组，最后遍历d数值去最大值。
-------------------------------------分割线------------------------------------------
上面算法的时间复杂度是O(n^2)，虽然可以过course.buaa.edu.cn上的测试题，但那还是因为测试点太弱，数据要求n可以取到10000，O(n^2)复杂度的算法必须超时。
在此我们介绍算法二。
算法二：
数据定义补充：
除了算法一的定义之外，加入b[]
b[k] ：在当前状态下，查找最长上升子序列的长度是k的序列，获取每一个序列的最后一项，这些项中的最小值就是b[k]。
用公式表达就是:
假设当前状态是a中的第t个数字，即遍历a数组执行到了第t次循环。
b[k] = Min{a[i]} (d[i] == k && 0 <= i < t)
b序列是严格递增的，即b[1] < b[2] < ... < b[t]。
证明：
若b[i] >= b[i + 1]
b[i + 1] 是长度为i+1的递增子序列的尾项的最小值，设此序列为x[1]..x[i+1]，x[1]..x[i]即构成长度为i的递增子序列，x[i] < x[i+1] = b[i+1] <= b[i]，与b[i]定义不符。
证毕#
算法：
// 遍历a数组
// 设当前状态是a中的第t个数字，即遍历a数组执行到了第t次循环。
// 设当前已经求出的最长上升子序列长度为len。
if a[t] > b[len]
// 将a[t]接在b[len]所代表的子串之后得到一个更长的子序列
len = len + 1
b[len + 1] = a[t]
else
// 找到这样一个j，使得b[j] < a[t] && b[j + 1] >= a[t]
// 即最大j使得b[j]的小于a[t]
b[j + 1] = a[t]
return : len
算法分析：
内层循环由于b序列的严格递增性，可以使用二分查找，时间复杂度为O(log n)，乘以外层循环，最终时间复杂度为O(n log n)。