最长不下降子序列（LIS）

题目描述

设有由 $n$ 个不相同的整数组成的数列，记为: $a_1$ 、 $a_2$ 、 $\dots$ 、 $a_n$ 且 $a_i \neq a_j$ ( $i \neq j$ )。 例如 $3$ ， $18$ ， $7$ ， $14$ ， $10$ ， $12$ ， $23$ ， $41$ ， $16$ ， $24$ 。 若存在 $i_1 \lt i_2 \lt i_3 \lt \dots \lt i_e$ 且有 $a$ $i1$ $\lt a$ $i2$ $\lt \dots \lt a$ $ie$ ，则称为长度为 $e$ 的不下降序列。 如上例中 $3$ ， $18$ ， $23$ ， $24$ 就是一个长度为 $4$ 的不下降序列，同时也有 $3$ ， $7$ ， $10$ ， $12$ ， $16$ ， $24$ 长度为 $6$ 的不下降序列。 程序要求，当原数列给出之后，求出最长的不下降序列。

输入格式

第一行为 $n$ ，表示 $n$ 个数（ $10 \le n \le 10000$ ）； 第二行 $n$ 个整数，数值之间用一个空格分隔（ $1 \le a_i \le n$ ）；

输出格式

最长不下降子序列的长度。

3
1 2 3

3

10
3 18 7 14 10 12 23 41 16 24

6

提示

无