- 2022tysc0158 的博客
【模板】最长不下降子序列
- 2023-11-8 11:24:13 @
#include<algorithm>
#include<cstdio>
using namespace std;
int n,a[100001],tails[100001],tot;
int LIS(){
tails[++tot]=a[1];
for(int i=2;i<=n;i++){
int p=upper_bound(tails+1,tails+tot+1,a[i])-tails;
if(p==tot+1&&a[i]>=tails[p])tails[++tot]=a[i];
else tails[p]=a[i];
}
return tot;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
printf("%d",LIS());
}