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)