A1628 | $最长上升子序列$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个长度为 $n$ 的序列 $a$，求其最长上升子序列的长度。 **子序列**：从序列中删除若干元素后，其他元素保持原顺序拼接组成的序列。例如对于序列 $[1,2,3,4,5]$ 来说，$[1,3], [2,3,4],[1,2,3,4,5], [4]$ 是它的子序列，$[3,2], [1,6], [1,2,2]$ 不是它的子序列。 **上升** ：对于一个长度为 $m$ 的序列 $b_1, b_2, \cdots, b_m$ ，若对于所有 $i\in [1, m - 1]$ 都满足 $b_i \lt b_{i+1}$， 则称该序列 $b$ 是上升的。 你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入的第一行是序列的长度$n(1 \leq n \leq 1000)$。 第二行给出序列中的 $n$ 个整($0 \leq a_i \leq 10000$)。

最长上升子序列的长度

输入 #1

7
1 7 3 5 9 4 8

输出 #1

C++ 编辑器

输入

输出