题意：给定n个整数，求Ai-Aj的最大值（i<j)， 2<=n<=100000
分析：简单模拟的话，用二重循环，O（n2）的复杂度肯定不行。对于每个Aj，只需要Ai最大就行，而最大的Ai可以通过相邻元素的比较获得，那么接下来枚举Aj即可，转化成O（n）
代码：
View Code
1 #include <stdio.h> 2 #include <iostream> 3 #define DEBUG 4 using namespace std; 5 const int MAXN = 10000 + 10; 6 int a[MAXN]; 7 int main(){ 8 #ifndef DEBUG 9 freopen("in.txt", "r", stdin); 10 #endif 11 int cas; 12 scanf("%d", &cas); 13 while(cas--){ 14 int n; 15 scanf("%d", &n); 16 int i, j; 17 for(i=0; i<n; i++) scanf("%d", &a[i]); 18 int ans = a[0]-a[1]; 19 int maxai = a[0]; 20 for(j=1; j<n; j++){ 21 ans = max(ans, maxai-a[j]); 22 maxai = max(maxai, a[j]); 23 } 24 printf("%d\n", ans); 25 } 26 return 0; 27 }
话说uva这题挂掉了，提交上去是RE，等待它修好了再提交吧。
