AcWing 896. 最长上升子序列 II
原题链接
中等
作者:
dooasyou
,
2024-03-25 21:34:12
,
所有人可见
,
阅读 1
时间复杂度 O(nlogn)
C++ 代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010;
int a[N],q[N];
int n;
int search_R(int l,int r,int x){
while(l<r){
int mid=l+r+1>>1;
if(q[mid]<x) l=mid;//严格递增不取等
else r=mid-1;
}
return l;
}
/*int search_L(int l,int r,int x){
while(l<r){
int mid=l+r>>1;
if(q[mid]>=x) r=mid;
else l=mid+1;
}
return l;
}*/
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
q[0]=-2e9;//初始q[0]负无穷,q[++len]=a[i]才能执行
int len=0;//前i个数中最大的最长上升子序列的值
for(int i=0;i<n;i++){// 从短到长解决各个子串的 LIS
int l=0,r=len;// 二分搜索,得到能接在 a[i] 前面的上升子序列的最大长度 l
if(a[i]>q[len]) q[++len]=a[i];
else q[search_R(l,r,a[i])+1]=a[i];
// else q[search_L(l,r,a[i])]=a[i];
}
//q是从0开始没错,虽然0位置置无穷而且q的更新不用0位置,但是用二分0位置要加上,因为q从0到len位置
//这份代码找左找右代码均可执行,因为大则添加,小则替换分开了
printf("%d",len);
return 0;
}