• 题意：
  • 给出n个数，问你这个序列的最长非下降的子序列的长度是多少
  • 代码：
    #include <bits/stdc++.h>
using namespace std;
int dp[1000010],a[1000010];
int f(int x)
{
  int len = 1,l,r,mid;
  dp[1] = a[1];
  for(int i=2;i<=x;i++)
  {
      l = 1;
      r = len;
      while(l <= r){
          mid = (l+r)/2;
          if(a[i] >= dp[mid])
              l = mid + 1;
          else
              r = mid - 1;
      }
      dp[l] = a[i];
      if(l > len)
          len = l;
  }
  return len;
}
int main()
{
  int n,k1,k2,ans;
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
      cin>>a[i];
  }
  ans = f(n);
  cout<<ans<<endl;
  return 0;
}

```