#4487. 萤石(GlowStone)

萤石(GlowStone)

题目:萤石光亮区间

题目背景:

在《我的世界》这款沙盒游戏中,玩家可以挖掘各种矿石和矿物,其中 萤石(Glowstone)是一种特殊的矿石,它不仅可以用来制作灯光源,还具有发光的特性。玩家在矿洞中探索时,萤石的光亮度会受到周围环境的影响,可能会增大或减小。

你正在探索一个矿洞,记录下了每一块萤石的光亮度变化。你希望找到一段连续的矿石区间,使得该区间内的萤石光亮度尽可能 保持不下降,从而可以获得最长的光亮区域,帮助你在矿洞中建立一个持久的光源。

题目描述:

给定一个长度为 n1 ≤ n ≤ 100000)的整数数列 a[1], a[2], ..., a[n],代表在矿洞中每一块萤石的光亮度。你需要找到其中的 最长不下降子序列 的长度。

一个不下降子序列是一个由原数列中元素组成的子序列,要求该子序列中的元素满足:

a[i1]a[i2]a[ik]a[i_1] \leq a[i_2] \leq \dots \leq a[i_k]

其中,i1<i2<<iki_1 < i_2 < \dots < i_k

注意: 你不需要输出最长不下降子序列本身,只需要输出它的长度。

输入格式:

  • 第一行输入一个整数 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