一个数组求其最长递增子序列(LIS)
例如数组{3, 1, 4, 2, 3, 9, 4, 6}的LIS是{1, 2, 3, 4, 6}，长度为5，假设数组长度为N，求数组的LIS的长度,
需要一个额外的数组 LIS 来记录
长度从1 到 n 慢慢变长求解的过程中 对应长度的 最长递增子序列的最小的末尾元素
解决方法
长度为1时 {3}：
将3放入LIS中，表示长度为1的时候,{3}数组的最长递增子序列的最小微元素
LIS：{3}
只有一个元素，所以 最长递增子序列就是 {3},最长递增子序列的最小尾元素 就是3
长度为2时 {3,1}：
新加入的元素1<3 长度增加变成2时，新加入的元素1比长度为1的时候的 最长递增子序列的最小尾元素还小，所以新加入元素1不会引起最长递增子序列变长，所以需要将1 插入 LIS中，在LIS中找到最小的比1大的元素，替换该元素，完成长度为2 的时候 最长递增子序列的寻找，
LIS：{1}
1替换掉3 表示 在长度为2的时候{3，1}的最长递增子序列的最小尾元素是1，验证 最长递增子序列{1}或{3}
长度为3时 {3,1,4}：
新加入的元素4>1,新加入的元素，比长度为2时的最长递增序列的最小尾元素大，说明新加入元素可以引起最长递增序列的增长，加入新元素4得：
LIS：{1，4}
验证 最长递增序列 {3,4} 或者 {1,4}
长度为4时 {3,1,4,2}：
新加入元素2<4, 比长度为3时的最长递增子序列的最小尾元素小，说明不引起最长递增序列的增长，需要在LIS中找到替换的元素 找到第一个比2大的元素4替换，这样在保证递增序列数量不变的情况下，将递增序列的范围往小值方向移动。得
LIS：{1，2}
验证 最长递增序列 {3,4} 或者 {1,2}
长度为5时 {3,1,4,2，3}：
新加入元素3>2, 比长度为4时的最长递增子序列的最小尾元素大，说明引起最长递增序列的增长，得
LIS：{1，2,3}
验证 最长递增序列 {1,2,3}
长度为6时 {3,1,4,2,3,9}：
新加入元素9>3, 比长度为5时的最长递增子序列的最小尾元素大，说明引起最长递增序列的增长，得
LIS：{1,2,3,9}
验证 最长递增序列 {1,2,3,9}
长度为7时 {3,1,4,2,3,9,4}：
新加入元素4<9, 比长度为3时的最长递增子序列的最小尾元素小，说明不引起最长递增序列的增长，需要在LIS中找到替换的元素 找到第一个比4大的元素9替换，这样在保证递增序列数量不变的情况下，将增序列的范围往小值方向移动。得
LIS：{1,2,3,4}
验证 最长递增序列 {1,2，3，4}
长度为8时 {3,1,4,2,3,9,4，6}：
新加入元素6>4, 比长度为7时的最长递增子序列的最小尾元素大，说明引起最长递增序列的增长，得
LIS：{1,2,3,4，6}
验证 最长递增序列 {1,2，3，4，6}
需要注意：
LIS保存的是 求解的过程中 对应长度的 最长递增子序列的最小的末尾元素 不一定就是最长递增序列原来的序列
插入新元素寻找替换位置的时候 有序查找可以使用二分查找 时间复杂度 o(LogN)
所以该解决方法的时间复杂度NlogN
空间复杂度 N