AcWing 896. 最长上升子序列 II
原题链接
中等
作者:
邓汪涛
,
2021-02-08 20:19:08
,
所有人可见
,
阅读 291
#include <iostream>
#include <cstring>
using namespace std ;
const int maxn = 1e5+5,inf = 0x3f3f3f3f;
int a[maxn];
int q[maxn];
int main()
{
memset(q,0x3f,sizeof q);
int n;scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
int res = 0;
q[0]=-inf; //如果q[]的每个值逗比要找的值要大 ,那么要保证最后一定找到q[0] (设置为-∞)
q[1]=a[1]; //长度为1的递增序列的最小值为a[1]
for(int i=2;i<=n;++i) //遍历整个序列
{
//二分查找 <a[i]的最后一个值
int l=0,r=n;
while(l<r)
{
int mid = l+r+1 >>1;
if(q[mid]>=a[i]) r=mid-1;
else l=mid;
}
//printf("q[%d]=%d\n",l,q[l]);
if(a[i]<q[l+1])
q[l+1]=a[i];
res = max(res,l+1);
}
printf("%d\n",res);
return 0;
}