当前位置: 代码迷 >> 综合 >> CODE[VS] 3955 最长严格上升子序列(加强版)
  详细解决方案

CODE[VS] 3955 最长严格上升子序列(加强版)

热度:86   发布时间:2024-01-19 02:38:43.0

题目描述 Description

给一个数组a1, a2 ... an,找到最长的上升降子序列ab1<ab2< .. <abk,其中b1<b2<..bk。

输出长度即可。


输入描述 Input Description

第一行,一个整数N。

第二行 ,N个整数(N < = 1000000)


输出描述 Output Description

输出K的极大值,即最长不下降子序列的长度

样例输入 Sample Input

5

9 3 6 2 7



样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

n<=1000000

为了方便大家调试,数据名称已被修改——THREE

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ologn求最长上升子序列~

今天检查才发现原来的少了一个return l,CODE[VS]是对的……


#include<cstdio>
#define ll long longll n,a[1000001],d[1000001],len;ll findd(ll u)
{ll l=1,r=len;while(l<r){ll mid=(l+r)>>1;if(d[mid]>=u && d[mid-1]<u) return mid;else if(d[mid]<u) l=mid+1;else r=mid-1;}return l;
}int main()
{scanf("%lld",&n);for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);d[++len]=a[1];for(ll i=2;i<=n;i++){ll j;if(a[i]>d[len]) j=++len;else if(a[i]<d[1]) j=1;else j=findd(a[i]);d[j]=a[i];}printf("%lld\n",len);return 0;
}


  相关解决方案