题目：最长上升子序列 II

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

第二行包含 N个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤1000001≤N≤100000，
−109≤数列中的数≤109−109≤数列中的数≤109

输入样例：

7

3 1 2 1 8 5 6

输出样例：

4

问题解决

 

这个问题我用dp+二分的方法来写。

一、 遍历a[i]将a[i]放入dp数组

1.1构造dp[i]数组：

　　dp[i]为长度是i的上升子序列结尾元素。
　　i:表示子序列的长度，取值范围是1~len，其中len表示目前最大的子序列长度。
1.2 将a[i]放入dp数组中
　　规则为找到某个dp[j],使得a[i]>dp[j]&&a[i]<dp[j+1],
　　找到后将dp[j+1]替换为a[i]，更新len 判断len是否因dp数组的扩大而变大，len=max(len,j+1)。
...........................................................................................................................................................................................................

二 、在dp[1]和dp[len]之间寻找满足1.2条的位置

2.1 L端起点和r端终点的初始选择
　　因为dp[i]的取值范围是1~len所以起始边界设置在两端之外L=0，r=len+1;
2.2 退出二分的条件
　　当L+1==r时说明两个指针已经相邻，边界已经找到即可退出循环。
2.3 L端和r端分界线的判定条件
　　L端都<a[i],r端都>=a[i]，满足l端条件L=mid，否则r=mid。
2.4 采用r
　　r即为1.2中的j+1。

我用的是手写二分法，主要参考链接如下：

https://www.bilibili.com/video/BV1d54y1q7k7?from=search&seid=14378360076371462119

大家也可以用upper_bound来取得r值。

3 总结

该程序时间复杂度为O(n*log n)，可以解决n=1e5的规模的问题。

程序君