301001 - 最长不下降子序列

题解bytaotao

用STL来做的最长不下降子序列

#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;
  cout<<"你听懂了吗!"<<'\n';
}