UVa11078:Open Credit System

题目大意

给定一个数组A，求A_i-A_j的最大值(i<j)

要求复杂度:Ο(n)

Solution

对给定的j，为了A_i-A_j取得最大值，A_i应该取最大，因此可以用一个变量maxA维护最大值，边读边计算答案。

AC-Code(C++)

Time:50ms

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 30000 + 10;

int main(int argc, const char * argv[]) {
    
//    freopen("input.txt", "r", stdin);
    
    int n,T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int maxA;
        scanf("%d",&maxA);
        int ans = -INF;
        int temp;
        for(int i=1;i<n;i++){
            scanf("%d",&temp);
            ans = max(ans,maxA-temp);
            maxA = max(maxA,temp);
        }
        
        printf("%d
",ans);
    }
    return 0;
}