问题 1300. -- 朱神的烦恼

1300: 朱神的烦恼

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

题目描述

众所周知,朱神作为XDUACM中极其优秀的人,无论是学习还是敲代码。
毫无疑问,当他开始找实习时,对于bat的offer那是拿得满满的。
可是对于众多offer,朱神产生了选择困难症,每个公司都想高薪聘请他,朱神不知道究竟该去哪。于是朱神通过自己创造的一个算法选择了最终的实习公司,
但这个算法中朱神有一个简单的问题没有解决,对于长度为n的整数序列{an},找出两个整数ai和aj(i<j),使得ai-aj的值最大,并输出这个最大的值。
由于朱神还要去收割更多的offer,他把这个简单的问题丢给了他的队友yeleng。
菜鸡yeleng在你的帮助下,找到了一个解决该问题的好办法,可是当他把方法告诉朱神的时候。
朱神一脸不屑的看着他说,你就不能好好看看数据范围吗,这肯定过不了啊!
yeleng再次思考了三天三夜仍然找不到能解决朱神问题的方法,你能不能再次帮帮他?

输入

第一行输入测试组数T。对于每组数据,第一行输入n,1<=n<=100000,紧接着输入一行,n个整数,第i个数字代表a1,a2,…,an,其中1<=T<=20,1<=ai<=1000000000,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输出

来源

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