题解
贪心
代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
const int N=1e5+10;
int n,a[N],q[N],maxlen;//q[i]存放长度为i的序列的集合中的结尾可能的最小数
int main(void){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++){
int l=0,r=maxlen;
while(l<r){//此二分模版查找严格比a[i]小的最大的数
int mid=l+r+1>>1;
if(q[mid]<a[i]) l=mid;
else r=mid-1;
}
q[l+1]=a[i];//更新长度为l+1序列的最小末尾 a[i]不会比q[l+1]大 若a[i]>q[l+1] 那么 a[i]就放到q[l+2]了
maxlen=max(maxlen,l+1);
}
cout<<maxlen;
}