xdoj-1010(区间问题）

题目链接

1 扫描一遍不行扫描两遍呗

2 O(n)时间确定cd[i]  【max( a[k]-_min） _min是k+1~n的最小值。i<=k<=n】

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
const int N=1e5+7;
int a[N]; int n;
int cd[N];
int main ()
{
    int T; scanf ("%d",&T);
    while (T--) {
        scanf ("%d",&n);
        for (int i=1;i<=n;i++) scanf ("%d",&a[i]);
        int x=a[n]; int ans=-0x3f3f3f3f;
        for (int i=n-1;i>=1;i--) {
            ans=max (ans,x-a[i]);
            cd[i]=ans;
            x=max (x,a[i]);
        }
        x=a[1]; ans=-0x3f3f3f3f;  int t=-0x3f3f3f3f;
        for (int i=2;i<=n-2;i++) {
            ans=max(ans,a[i]-x);
            t=max (t,ans+cd[i+1]);
            x=min (x,a[i]);
        }
        printf("%d
",t);
    }
    return 0;
}