<center> 4171.   L-The math problem
Time Limit: 1.0 Seconds    Memory Limit:65536K
Total Runs: 287    Accepted Runs:86 </center>

Given an array a with n intergers, please tell me the max(ajai),0ijn1max(aj−ai),0≤i≤j≤n−1.

Input

The input consists of multiple test cases. The first line contains an integer TT, indicating the number of test cases.(1T1000)(1≤T≤1000)
Each case contains one integer NN.(0N107)(0≤N≤107). Then comes a line with N intergers ai(107ai107)ai(−107≤ai≤107)

Output

For each case only output the answer.

Sample Input

1
5
1 3 5 4 2

Sample Output

4

水题 直接扫一遍 维护最大差值

注意要看清题,j是大于等于i的


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;

int a[10000005];

int main()
{
	int t;
	while(~scanf("%d",&t))
	{
		while(t--){
			memset(a,0,sizeof(a));
			int n;
			scanf("%d",&n);
			for(int i=0;i<n;i++){
				scanf("%d",&a[i]);
			} 
			int max_dif=0;
			int minn=999999;
			for(int i=0;i<n;i++){
				if(minn>a[i]){
					minn=a[i];
				}
				if(a[i]-minn>max_dif){
					max_dif=a[i]-minn;
				}
			}
			printf("%d\n",max_dif);
		}
	}
	return 0;	
}