#include <bits/stdc++.h> using namespace std; int n,x[100001],Lis[100001],longest=0; /* 这道题用最长不下降子序列来做 就是用一个维护序列，始终保持最长不下降，相当于单调队列 */ int main() { cin>>n; for(int i=0; i<n; i++) { scanf("%d",&x[i]); if(!i) Lis[longest++]=x[i]; else { if(x[i]<Lis[longest-1])//如果比之前的最大数小的话，就要搜寻队列，寻找代替 { int j=upper_bound(Lis,Lis+longest,x[i])-Lis;//用STL里的upper_bound代替二分寻找 //维护队列的单调性 Lis[j]=x[i]; } else//其他情况直接添加在单调队列即可 { Lis[longest++]=x[i]; } } } printf("%d",longest);//这里longest不用减一，因为前面初始化为0 return 0; }