最长非下降子序列

  • 题意:
  • 给出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;
    }
    

```

全部评论

相关推荐

06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 17:37
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务