最长上升子序列

如果一个数列a_i 满足 a₁ < a₂ < ... < a_N 则这个数列被称作上升序列。

给定一个数列a(a₁, a₂, ..., a_N)则任意一个数列b(a_i1, a_i2, ..., a_iK)并且满足（1 <= i₁ < i₂ < ... < i_K <= N）.则b被称为a的子序列。

如果一个数列的子序列是上升序列，则这个序列称为原序列的上升子序列。

比如序列(1, 7, 3, 5, 9, 4, 8)的上升子序列有(1, 7), (3, 4, 8)等. 它的最长上升子序列长度是4,即(1, 3, 5, 8).

请你写一个程序求一个序列的最长上升子序列的长度。

第一行是一个整数N表示给定数列的长度. 第二行包括N个范围在0～10000的整数。 1 <= N <= 1000

输出一个整数表示最长上升子序列的最大长度

7
1 7 3 5 9 4 8

4