#4487. 萤石(GlowStone)
萤石(GlowStone)
题目:萤石光亮区间
题目背景:
在《我的世界》这款沙盒游戏中,玩家可以挖掘各种矿石和矿物,其中 萤石(Glowstone)是一种特殊的矿石,它不仅可以用来制作灯光源,还具有发光的特性。玩家在矿洞中探索时,萤石的光亮度会受到周围环境的影响,可能会增大或减小。
你正在探索一个矿洞,记录下了每一块萤石的光亮度变化。你希望找到一段连续的矿石区间,使得该区间内的萤石光亮度尽可能 保持不下降,从而可以获得最长的光亮区域,帮助你在矿洞中建立一个持久的光源。
题目描述:
给定一个长度为 n(1 ≤ n ≤ 100000)的整数数列 a[1], a[2], ..., a[n],代表在矿洞中每一块萤石的光亮度。你需要找到其中的 最长不下降子序列 的长度。
一个不下降子序列是一个由原数列中元素组成的子序列,要求该子序列中的元素满足:
其中, 。
注意: 你不需要输出最长不下降子序列本身,只需要输出它的长度。
输入格式:
- 第一行输入一个整数
n,表示数列的长度。 - 第二行输入
n个整数,表示数列a[1], a[2], ..., a[n]每一个元素范围是 [1, 1000],每个整数代表该位置的萤石光亮度。
输出格式:
输出一个整数,表示最长不下降子序列的长度。
样例输入 1:
8
1 3 2 4 5 7 3 8
样例输出 1:
6
样例输入 2:
4
9 7 4 5
样例输出 2:
2
样例输入 4:
6
3 3 3 3 3 3
样例输出 4:
6