UVa11078 Open Credit System

题目大意

给定一个长度为N的序列A，找出两个整数A[i]和A[j](i<j)，使得A[i]-A[j]尽量大

题解

最简单的做法就是直接用二重循环枚举A[i]和A[j]，不过对于N=10000的数据量显然会超时。对于每个j，我们要找到最大的A[i]，只要

在枚举j的时候顺便用一个变量维护一下A[i]的最大值就行，这样时间复杂度就由O(N^2)降低到O(N)了。

代码

#include<stdio.h>
#include<stdlib.h>
#define MAXN 100005
#define INF 0x7fffffff
long a[MAXN];
long MAXS;
long max(long a,long b)
{
    return a>b?a:b;
}
int main(void)
{
    long n,i,ans,T;
    scanf("%ld",&T);
    while(T--)
    {
        scanf("%ld",&n);
        for(i=0;i<n;i++)
        scanf("%ld",&a[i]);
        ans=-INF;
        MAXS=a[0];
        for(i=1;i<n;i++)
        {
        ans=max(ans,MAXS-a[i]);
        if(a[i]>MAXS)
        MAXS=a[i];
        }
        printf("%ld\n",ans);
    }
    return 0;
}