Problem E: 最长不下降子序列
[Creator : ]
Description
例如13,7,9,16,38,24,37,18,44,19,21,22,63,15的一个数字序列,可以有很多子序列。
如13 7 9是一个长度为3的子序列,13 9 44 19是一个长度为4的子序列。13,16,18,19,21,22,63是一个长度为7的不下降的子序列,同时也有7 ,9,16,18,19,21,22,63这个长度为8的不下降子序列。
不下降子序列的数学定义为:设有由n个整数组成的数列,记为:b(1)、b(2)、……、b(n),若存在i1<i2<i3< … < ie 且 有b(i1)<=b(i2)<= … <=b(ie)则称为长度为e的不下降序列。 当然,序列本身也是他自己的一个子序列。
要求一个给定序列的最长不下降子序列。
如13 7 9是一个长度为3的子序列,13 9 44 19是一个长度为4的子序列。13,16,18,19,21,22,63是一个长度为7的不下降的子序列,同时也有7 ,9,16,18,19,21,22,63这个长度为8的不下降子序列。
不下降子序列的数学定义为:设有由n个整数组成的数列,记为:b(1)、b(2)、……、b(n),若存在i1<i2<i3< … < ie 且 有b(i1)<=b(i2)<= … <=b(ie)则称为长度为e的不下降序列。 当然,序列本身也是他自己的一个子序列。
要求一个给定序列的最长不下降子序列。
Input
若干个数。个数不超过1000.
Output
最长不下降子序列的长度。
Sample Input Copy
13 7 9 16 38 24 37 18 44 19 21 22 63 15
Sample Output Copy
max=8
HINT
---
acg
32525
acg
32525