问题 5491 --经典 LIS

5491: 经典 LIS

题目描述

给出一个长度为 $n$ 的整数序列 $\{a_i\}$，求它包含的最长不下降子序列。

输入

第一行包含一个正整数 。 第二行包含 $n$ 个整数，其中第 $i$ 个整数表示 $a_i$。

输出

输出一行一个数表示答案。

样例输入输出

输入#1 复制 
5
2 3 5 6 4
输出#1 复制 
4

提示

对于 $30\%$ 的数据，$n \leq 8000$。 对于 $100\%$ 的数据，$1 \leq n \leq 5\times 10^5$，$|a_i| \leq 10^9$。
发表题解
序号 标题 作者 发表时间 费用 订购数 操作

题目信息

提交
难度
普及/提高-
标签
点击显示
递交数
2
已通过
1
通过率
50%
时间限制
1 秒
内存限制
128 MB
来源
入门模拟2
收藏