神偷

测试数据来自 system/1283

时间限制:1秒  内存限制:256M


【题目描述】

  李三是一个超级神偷,他最为突出的地方,就是他每次都能逃脱重重围堵,这是因为他有一个神奇的技能——滑翔。
  假设城市中一共有 \(N\) 幢建筑排成一条线,每幢建筑物有一个高度。初始时,李三可以在任何一幢建筑的顶端。他可以选择一个方向逃跑,但是不能中途改变方向(因为警察会在后面追击)。虽然滑翔是他的超级技能,但他只能往下滑行(即:只能从较高的建筑滑翔到较低的建筑)。他希望尽可能多地经过不同建筑的顶部,这样可以减缓下降时的冲击力,减少受伤的可能性。请问,他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)?

【输入格式】

  第一行是一个整数 \(N\),代表有 \(N\) 幢建筑。第二行包含N个不同的整数,每一个对应一幢建筑的高度 \(h\),按照建筑的排列顺序给出。

【输出格式】

  输出一行,包含一个整数,代表李三最多可以经过的建筑数量。

【输入输出样例1】

 Input

8
300 207 155 299 298 170 158 65

 Output

6

【输入输出样例2】

 Input

8
65 158 170 298 299 155 207 300

 Output

6

【输入输出样例3】

 Input

10
2 1 3 4 5 6 7 8 9 10

 Output

9

【数据限制】

  \(100\%\) 的数据满足: \(N <= 1000\), \(0 < h < 1000000\)

【来源】

  Mr.he

信息

ID
1883
难度
(无)
分类
动态规划 | LIS 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者