UVa 11078 Open Credit System

　　题目大意：给一个n个数的数组A[1...n]，从中找出两个数A[i], A[j](i<j) 使得A[i]-A[j]的值最大。　　

　　首先用二重循环试了下，超时。对于每一个j，只需找出左边最大的值就行了，因此从小到大枚举j，同时维护j左边的最大值lmax。

View Code

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <climits>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8 #ifdef LOCAL
 9     freopen("in", "r", stdin);
10 #endif
11     int T, x;
12     scanf("%d", &T);
13     while(T--)
14     {
15         int n;
16         scanf("%d", &n);
17         scanf("%d", &x);
18         int lmax = x;
19         int ans = INT_MIN;
20         for(int i = 1; i < n; i++)
21         {
22             scanf("%d", &x);
23             ans = max(ans, lmax-x);
24             lmax = max(lmax, x);
25         }
26         printf("%d\n", ans);
27     }
28     return 0;
29 }