【题目链接】 点击打开链接
【题意】
给定一个包含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]);
}