1385: 最长不下降序列
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:29
解决:7
题目描述
设有一个正整数的序列:b1,b2,…,bn,对于下标i1<i2<…<im,若有bi1≤bi2≤…≤bim
则称存在一个长度为m的不下降序列。
例如,下列数列
13 7 9 16 38 24 37 18 44 19 21 22 63 15
对于下标i1=1,i2=4,i3=5,i4=9,i5=13,满足13<16<38<44<63,则存在长度为5的不下降序列。
但是,我们看到还存在其他的不下降序列: i1=2,i2=3,i3=4,i4=8,i5=10,i6=11,i7=12,i8=13,满足:7<9<16<18<19<21<22<63,则存在长度为8的不下降序列。
问题为:当b1,b2,…,bn给出之后,求出最长的不下降序列
输入
n个数
输出
max=最长的不下降子序列长度
样例输入 复制
13 7 9 16 38 24 37 18 44 19 21 22 63 15
样例输出 复制
max=8
提示
个数n(1<=n<=1000)