D. (L3-11)最长上升子序列

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

一个数的序列 $bi$，当 $b1 < b2 < \dots < bS$的时候，我们称这个序列是上升的。

对于给定的一个序列 $(a1, a2, ..., aN)$，我们可以得到一些上升的子序列 $(ai1, ai2, ..., aiK)$，这里 $1 <= i1 < i2 < ... < iK <= N4$。

比如，对于序列 $(1, 7, 3, 5, 9, 4, 8)$，有它的一些上升子序列，如 $(1, 7), (3, 4, 8)$ 等等。

这些子序列中最长的长度是 $4$ ，比如子序列 $(1, 3, 5, 8)$.

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

第一行为 $n$ ，表示 $n$ 个数$(10 \leq n \leq 10000)$
第二行 $n$ 个整数，数值之间用一个空格分隔 $(1 \leq a(i) \leq n)$

最长上升子序列的长度

6
1 6 2 4 4 7