【题目链接】 点击打开链接

【题意】

给定一个包含n个元素的数组,我们可以把位置连续的数分为一组,每组至少包含一个元素。

每组对答案的贡献是这个组内最大的数和最小的数的差值。

对于单个元素组成的组,差值为0。输出答案的最大值,1 <= n <= 1e6, 第i个数大小ai(-1e9 <= ai <= 1e9)。

【解题思路】

定义i是峰值点,如果a[i-1]<=a[i]>=a[i+1]或者a[i-1]>=a[i]<=a[i+1],那么每一段中包含的峰值点一定在这一段的端点,否则从峰值点处将区间断开不会使结果变差,这也说明了存在最优解使得每一段是严格单调的,记dp[i]为把前i个数分段的最大得分,考虑i左侧最近的峰值点la,那么只需枚举la属于前一段还是后一段,于是有dp[i]=max(dp[la-1]+labs(a[i]-a[la]),dp[la]+labs(a[i]-a[la+1])),复杂度O(n)


【AC代码】


//
//Created by just_sort 2016/1/3
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b)     memset(a, b, sizeof(a))
#define MP(x, y)      make_pair(x,y)
const int maxn = 1e5 + 10;
const int maxm = 2e5;
const int maxs = 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
int gcd(int x, int y) {return y == 0 ? x : gcd(y, x % y);}
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
int n, a[1000010];LL dp[1000010];
int main()
{
    scanf("%d", &n);
    REP2(i, 1, n) scanf("%d", &a[i]);
    CLR(dp, 0);
    int la = 1;
    REP2(i, 2, n){
        dp[i] = max(dp[la - 1] + 1LL * abs(a[i] - a[la]) , dp[la] + 1LL * abs(a[i] - a[la + 1]));
        if(i < n && a[i - 1] <= a[i] && a[i] >= a[i + 1]) la = i;
        if(i < n && a[i-1] >= a[i] && a[i] <= a[i + 1]) la = i;
    }
    printf("%lld\n", dp[n]);
}