Uva 11078 简单dp

题目链接:http://uva.onlinejudge.org/external/110/11078.pdf

a[i] - a[j] 的最大值。

这个题目马毅问了我，O(n^2)超时，记忆化一下当前最大值。

#include <bits/stdc++.h>

using namespace std;

int A[100000],n;

int main()
{
    int t;
    cin>>t;
    while(t--) {
        cin>>n;
        for(int i=0;i<n;i++) {
            cin>>A[i];
        }
        int ans = -0x3f3f3f3f;
        int maxai = A[0];
        for(int i=1;i<n;i++) {
            ans = max(ans,maxai-A[i]);
            maxai = max(maxai,A[i]);
        }

        cout<<ans<<endl;
    }
    return 0;
}