#366. 最长上升子序列

最长上升子序列

题目描述

(LIS问题)给定一个序列,从中选取若干个数,使得这一组数组成上升子序列尽可能长,即对于所有的 i<j i \lt j 满足 ai<aja_i \lt a_j ,求这个序列的最长上升子序列的长度。

输入格式

第一行一个整数 nn 表示序列的长度

接下来一行 nn 个整数表示序列

输出格式

一行一个整数表示最长上升子序列的长度

样例

样例输入

5
1 5 1 2 4

样例输出

3

数据范围与提示

组成的数列为 11 22 44,不存在比这个更长的上升子序列

  • 对于 30%30\% 的数据, n2000n \le 2000

  • 对于 100%100\% 的数据,n100000n \le 100000