问题 1382. -- 机器人军团

1382: 机器人军团

时间限制: 1 Sec  内存限制: 128 MB
提交: 145  解决: 84
[提交][状态][讨论版]

题目描述

修罗王建造了一支机器人军团,机器人排成一行,且身高分别为b1,b2,…,bn。修罗王准备从中选出一组满足最长不下降子序列规则的机器人组成一支精锐卫队。
所谓不下降子序列(Longest Increasing Subsequence,LIS)定义为:设有由n个不相同的整数组成的数列b[n],若有下标i1<i2<…<iL且b[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≤10000)个数。第二行为n个数的值。

输出

一个整数,即最长不下降序列的长度。

样例输入

4
1 3 1 2

样例输出

2

提示

来源

[提交][状态]