AcWing 896. 最长上升子序列 II
原题链接
中等
作者:
acid001011
,
2022-02-23 16:41:44
,
所有人可见
,
阅读 174
题目
思路:贪心+二分
- 贪心思路
较小的数开头的数作为的子序列 比 较大的数作为开头的子序列 更好
这里的“好”体现在后面的数更容易接上
如果能接上较大的数,那一定能接上较小的数,所以可以每次贪心的取较小的数。(因此这么贪心不影响正确性)
- 维护一个数组q,$q[i]$表示长度为i的子序列的末尾最小元素值,处理完以后的q数组大小即为最长上升子序列的长度。
遍历初始数组:
如果碰到的值大于当前q数组中的最后一个值,那么就把这个值放到数组后面;
如果碰到的值小于等于当前q数组中的最后一个值,那么就用它来替代q数组中第一个大于或等于它的值。(通过二分来查找)
时间复杂度:$O(nlogn)$(状态规模为$n$,状态转换方程计算时间为$logn$)
代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n;
int main()
{
scanf("%d",&n);
vector<int> num(n);//这里要开n的空间,不开就是错的
for(int i=0;i<n;i++) scanf("%d",&num[i]);
vector<int> stk;//模拟堆栈
stk.push_back(num[0]);
for(int i=1;i<n;i++)
{
if(num[i]>stk.back())
stk.push_back(num[i]);//如果该元素大于栈顶元素,将该元素入栈
else
*lower_bound(stk.begin(),stk.end(),num[i])=num[i];//替换掉第一个大于或者等于这个数字的那个数
}
printf("%d",stk.size());
return 0;
}