问题 24328 --最长不降子序列

24328: 最长不降子序列

时间限制: 1 Sec  内存限制: 128 MB
提交: 21  解决: 10
[提交][状态][讨论版][数据上传:][下载FPS1元][添加到购物车][下载测试数据1元][60kb]

题目描述

【问题描述】
设有由n个不相同的整数组成的数列,记为:a(1)、a(2)、……、a(n)
例如3,18,7,14,10,12,23,41,16,24。
若存在:i1 < i2 < i3 < … < ie 且有:a(i1) <= a(i2) <= … <= a(ie)则称为长度为e的不下降序列。
如上例中3,18,23,24就是一个长度为4的不下降序列,同时也有3,7,10,12,16,24长度为6的不下降序列。

程序要求,当原数列给出之后,求出最长的不下降序列的长度以及序列的每个元素。

Input

 一个数n
以下一行是长度为n的序列。

Output

 给出序列的最长不降子序列的长度

Sample Input

10
3 18 7 14 10 12 23 41 16 24 

Sample Output

6 

Hint

1 <= n <= 1000
a[i]<100000000

本题没有 a(i)<>a(j) (i<>j) 的前提限制

输入

输出

提示

来源

[提交][状态]