问题 1299. -- 朱神的序列

1299: 朱神的序列

时间限制: 1 Sec  内存限制: 128 MB
提交: 465  解决: 138
[提交][状态][讨论版]

题目描述

众所周知,朱神作为XDUACM中极其优秀的人,无论是学习还是敲代码。
毫无疑问,当他开始找实习时,对于bat的offer那是拿得满满的。
可是对于众多offer,朱神产生了选择困难症,每个公司都想高薪聘请他,朱神不知道究竟该去哪。于是朱神通过自己创造的一个算法选择了最终的实习公司,
但这个算法中朱神有一个简单的问题没有解决,对于长度为n的整数序列{an},找出两个整数ai和aj(i<j),使得ai-aj的值最大,并输出这个最大的值。
由于朱神还要去收割更多的offer,他把这个简单的问题丢给了他的队友yeleng。
可是菜鸡yeleng想了好久都想不出来如何解决这个问题,而他还要进行期中考试的复习,你能帮帮他吗?

输入

第一行输入测试组数T。对于每组数据,第一行输入n,2<=n<=10000,紧接着输入一行,n个整数,第i个数字代表a1,a2,…,an,其中1<=T<=10,1<=ai<=10000,1<=i<=n.

输出

每组数据输出一行结果,该行仅包含一个整数,表示该组数组ai-aj(i<j)的最大值

样例输入

2
3
3 2 1
4
13 8 7 1

样例输出

2
12

提示

对于第二组数组,ai-aj(i<j)的结果分别为5、6、12、1、7、6,在这些数字中选择最大的数字12输出

来源

[提交][状态][讨论版]