uva11078Open Credit System

题意：给定n个整数，求Ai-Aj的最大值（i<j)， 2<=n<=100000

分析：简单模拟的话，用二重循环，O（n²）的复杂度肯定不行。对于每个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，等待它修好了再提交吧。