OpenJudge

2938:机器人军团

总时间限制:
5000ms
单个测试点时间限制:
1000ms
内存限制:
131072kB
描述

      话说在天顶星人的指导下,修罗王建造了一支机器人军团,机器人排成一行,且身高分别为b1b2,……bn。修罗王准备从中选出一组满足最长不下降子序列规则的机器人组成一支精锐卫队。

      所谓不下降子序列(LIS)定义为:设有由n个不相同的整数组成的数列b[n],若有下标i1 < i2 < …… < iLb[i1] < b[i2] < …… < b[iL],则称存在一个长度为L的不下降序列。

      例如13,7,9,16,38,24,37,18,44,19,21,22,63,15。有13 < 16 < 38 < 44 < 63长度为5的不下降子序列。但经过观察,实际还有7 < 9 < 16 < 18 < 19 < 21 < 22 < 63长度为8的不下降子序列。那么是不是还有更长的不下降子序列呢?请找出最长不下降子序列的长度。

输入
第一行为n,表示n(n <= 100 000)个数。第二行为n个数的值。
输出
一个整数,即最长不下降序列的长度。
样例输入
4
1 3 1 2
样例输出
2
来源
BD
全局题号
15431
添加于
2017-07-05
提交次数
23
尝试人数
15
通过人数
15