一、题目查看

题目描述：

对于一个数的序列bi，当b1<b2<...<bS的时候，我们称这个序列是上升的。

对于给定的一个序列(a1​,a2​,...,an​)，我们可以找到一些上升的子序列(ai1,ai2,...,aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).

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

输入格式：

第一行输入一个整数n

第二行输入n个整数

输出格式：

输出一个整数，表示最长递增子序列的长度

样例输入：​

7 1 7 3 5 9 4 8
样例输出：

4