#3956. 1281. 最长上升子序列

1281. 最长上升子序列

题目描述

一个数的序列 bib_i,当 b1<b2<…<bSb_1 < b_2 < \ldots < b_S 的时候,我们称这个序列是上升的。对于给定的一个序列 (a1,a2,…,aN)(a_1, a_2, \ldots, a_N),我们可以得到一些上升的子序列 (ai1,ai2,…,aiK)(a_{i_1}, a_{i_2}, \ldots, a_{i_K}),这些下标满足 1≤i1<i2<…<iK≤N1 \le i_1 < i_2 < \ldots < i_K \le N。

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

输入格式

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

输出格式

最长上升子序列的长度。

7
1 7 3 5 9 4 8
4

来源

一本通在线评测 ybtbas-1281