4160 - 动态规划:最长上升子序列

通过次数

42

提交次数

81

时间限制 : 1 秒
内存限制 : 128 MB

一个数的序列b_i,当b_1 < b_2 < ... < b_S的时候,我们称这个序列是上升的。对于给定的一个序列(a_1, a_2, ..., a_N),我们可以得到一些上升的子序列(a_i _1, a_i _2, ..., a_i _K),这里1 <= i_1 < i_2 < ... < i_K <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8).

你的任务,就是对于给定的序列,求出最长上升子序列的长度。

输入

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。

输出

最长上升子序列的长度。

样例

输入

7
1 7 3 5 9 4 8

输出

4