2 shunfurh shunfurh 于 2017.08.28 14:06 提问

Deque

Problem Description
Today, the teacher gave Alice extra homework for the girl weren't attentive in his class. It's hard, and Alice is going to turn to you for help.
The teacher gave Alice a sequence of number(named A) and a deque. The sequence exactly contains N integers. A deque is such a queue, that one is able to push or pop the element at its front end or rear end. Alice was asked to take out the elements from the sequence in order(from A_1 to A_N), and decide to push it to the front or rear of the deque, or drop it directly. At any moment, Alice is allowed to pop the elements on the both ends of the deque. The only limit is, that the elements in the deque should be non-decreasing.
Alice's task is to find a way to push as many elements as possible into the deque. You, the greatest programmer, are required to reclaim the little girl from despair.

Input
The first line is an integer T(1≤T≤10) indicating the number of test cases.
For each case, the first line is the length of sequence N(1≤N≤100000).
The following line contains N integers A1,A2,…,AN.

Output
For each test case, output one integer indicating the maximum length of the deque.

Sample Input
3
7
1 2 3 4 5 6 7
5
4 3 2 1 5
5
5 4 1 2 3

Sample Output
7
5
3

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.11 23:43
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Java 数据结构之Deque的几种实现
1、ArrayDeque 2、ConcurrentLinkedListDeque 3、I
Java 数据结构之Deque(双端队列)
Deque接口是“double ended queue”的缩写(通常读作“deck”),即双端队列,支持在队列的两端插入和删除元素。大多数的实现对元素的数量没有限制,但这个接口既支持有容量限制的deque,也支持没有固定大小限制的。 Deque接口定义了在两端访问元素的方法,主要包括insert、remove和examine。和Queue定义一样,所有这些方法存在两种形式:一种如果操作失败则抛出
C++ Deque容器的使用方法
Deque容器的使用方法     容器deque和vector非常相似,操作函数基本一致。它采用动态数组来管理元素,提供随机存取,可以在头尾两端进行快速安插和删除元素操作。特别要注意,除了头尾两端,在任何地方安插与删除元素,都将导致指向deque元素的任何pointers references iterators 失效。   包括的头文件为: #include using na
python中deque模块详解
最近在pythonTip做题的时候,遇到了deque模块,以前对其不太了解,现在特此总结一下 deque模块是python标准库collections中的一项,它提供了两端都可以操作的序列,这意味着,在序列的前后你都可以执行添加或删除操作。 1.创建deque序列: from collections import deque d=deque() 2.deque提供了类似list的操作方法
stl deque使用详解
一、 Deque阐述             deque和vector都是顺序性容器,deque容器是C++标准模版库(STL,Standard Template Library)中的部分内容。deque容器类与vector类似,支持随机访问和快速插入删除,它在容器中某一位置上的操作所花费的是线性时间。与vector不同的是,deque还支持从开始端插入数据:push_front()。dequ
deque及迭代器失效问题
deque由一段一段的定量连续空间构成,采用一个表(map)来记录每个连续空间的首址,map是一小块连续的空间,目的是便于迭代器的寻址(map+1即可跳转到下一个连续空间的首址)。map中的每一个元素(node)都是指针,指向另一端(较大的)连续线性空间,称为缓冲区,缓冲区才是deque的储存空间主体。具体机制如下所示: 其中,对迭代器it的解引用得到的是cur位置处对应的元素。 de
C++中的deque总结
Deque双端队列容器 一、基本原理     deque的元素数据采用分块的线性结构进行存储,如图所示。deque分成若干线性存储块,称为deque块。块的大小一般为512个字节,元素的数据类型所占用的字节数,决定了每个deque块可容纳的元素个数。 所有的deque块使用一个Map块进行管理,每个Map数据项记录各个deque块的首地址。Map是deque的中心部件,将先于deque块,依
deque的构造与内存管理
deque与vector的差异: 1 deque允许于常数时间对头端进行插入或移除操作 2 deque没有容量(capacity)观念,因为它是以动态地分段连续空间(中控器)组合而成 3 deque避免了“重新配置、复制、释放”的轮回,代价则是复杂的迭代器架构。 迭代器++:切换至下一个元素,如果已达所在缓冲区的尾端,就却换至下一节点(即下一缓冲区)的第一个元素。
C++ STL之deque详解
deque容器deque容器是C++ STL中的内容。deque与vector类似,支持随机访问和快速插入删除。deque还支持从开始端加入数据:push_front()构造函数deque<Elem> d;//创建一个空的deque deque<Elem> d1(d2);//复制一个deque ~deque<Elem>();//销毁所有数据,释放内存成员函数deque.begin();//返回指向第
【vc】【STL源码】vector,deque与sort的用法比较及入门
#include stdio.h> // sort的定义 #include algorithm> // vector的定义 #include vector> // deque的定义 #include deque> // 同样,引入std命名空间 using namespace std; // 用数组保存 int friends[1000]; // 用vector保存 vectorint> vt