AcWing 896. 基础课二刷之第54题加强巩固 最长上升子序列 II*
原题链接
中等
作者:
Snow_raw
,
2021-08-20 18:19:21
,
所有人可见
,
阅读 182
题目描述
给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤100000,
−109≤数列中的数≤109
样例
7
3 1 2 1 8 5 6
输出
4
算法
二分
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int cnt;
int f[N];
int a[N];
int find(int x){
int l=1,r=cnt;
while(l<r){
int mid=l+r>>1;
if(f[mid]>=x)r=mid;
else l=mid+1;
}
return r;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
f[++cnt]=a[1];
for(int i=2;i<=n;i++){
if(a[i]>f[cnt])f[++cnt]=a[i];
else{
int tmp=find(a[i]);
f[tmp]=a[i];
}
}
cout<<cnt<<endl;
return 0;
}
总结
如果碰到比当前最大的还大入队,否则将第一个大于等于该数的数替换掉