最长上升子序列 II

题目:最长上升子序列 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的规模的问题。

程序君

上一篇:蓝桥杯2015年第六届C/C++A组国赛第四题-穿越雷区


下一篇:链表操作(创建空链表、头插法、尾插法、反转链表、修改、删除链表元素、获取链表元素位置)