Comfortable Formation

简介: 该文章是关于解决“Comfortable Formation”问题的算法题解,其中描述了如何从给定的数列中选择一部分人形成一个新的对称且单调递增的队形,并保持原数列中数的相对顺序不变,目的是找出能组成的最长舒服队列。

Comfortable Formation

风吹落叶上大学后眼睛近视有点重,不戴眼镜的时候喜欢看比较舒服队列而且越长越好,不舒服的队列看了眼睛有点难受感觉不是很好。
  假设有n个人按顺序站在他的面前,他们的身高分别是h[1], h[2] … h[n],风吹落叶希望从中挑出一些人,让这些人形成一个新的队形,新的队形若满足以下三点要求,则就是新的舒服队形:
  1、挑出的人保持原队形的相对顺序不变,且必须都是在原队形中连续的;
  2、左右对称,假设有m个人形成新的队形,则第1个人和第m个人身高相同,第2个人和第m-1个人身高相同,依此类推,当然如果m是奇数,中间那个人可以任意;
  3、从左到中间那个人,身高需保证不下降,如果用H表示新队形的高度,则H[1] <= H[2] <= H[3] … <= H[mid]。

现在风吹落叶看前面那么多人有点蛋疼,请问牛高马大的你能帮帮我,找出最长的舒服队列吗?
  
  Input
  输入数据第一行包含一个整数T,表示总共有T组测试数据(T <= 20);
  每组数据首先是一个整数n(1 <= n <= 100000),表示原先队形的人数,接下来一行输入n个整数,表示原队形从左到右站的人的身高(50 <= h <= 250,不排除特别矮小和高大的)。
  Output
  请输出能组成舒服队形的最多人数,每组输出占一行。

相关文章
|
前端开发 JavaScript 定位技术
高德客户端及引擎技术架构演进与思考
高德客户端及引擎技术架构演进与思考
|
机器学习/深度学习 存储 算法
【算法分析与设计】贪心算法(上)
【算法分析与设计】贪心算法(上)
|
数据可视化
Hisat2+FeatureCounts+DESeq2流程+作图!
Hisat2+FeatureCounts+DESeq2流程+作图!
|
传感器 数据采集 ice
Google Earth Engine ——LANDSAT 7Collection 1 Tier 1 DN值 RAW数据集
Google Earth Engine ——LANDSAT 7Collection 1 Tier 1 DN值 RAW数据集
281 0
Google Earth Engine ——LANDSAT 7Collection 1 Tier 1 DN值 RAW数据集
|
Kubernetes 容器 Perl
kubernetes管理集群系列之命令行工具kubectl详解(2.2)
kubernetes管理集群系列之命令行工具kubectl详解
249 0
|
网络协议 Dubbo 关系型数据库
分库分表就能无限扩容吗?
让我们从最初开始。 1、单体应用 每个创业公司基本都是从类似 SSM 和 SSH 这种架构起来的,没什么好讲的,基本每个程序员都经历过。 2、RPC 应用 当业务越来越大,我们需要对服务进行水平扩容,扩容很简单,只要保证服务是无状态的就可以了,如下图:
213 0
分库分表就能无限扩容吗?
|
测试技术
《MonoTouch开发实践指南》一1.4 使用MonoTouch调试器
本节书摘来自华章出版社《MonoTouch开发实践指南》一 书中的第1章,第1.4节,作者:(美)Michael Bluestein,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1129 0