← 返回题单

题单练习动态规划基础

← 上一题下一题 →

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++ 编辑器

输入

输出