http://codeforces.com/contest/789/problem/C
首先按题目要求处理出dis数组。
那么对于任意一个区间,[L, R],是dis[L] – dis[L + 1] + dis[L + 2] …. +
那么怎么知道是+还是—呢?
注意到对于一个数,要么是正,要么是负。
考虑第一个数,是正的时候,第三个数肯定是取正,第二个数肯定只能是负。
那么就是对这个数组求一次最大字段和
同理第一个数是负数的情况。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e5 + ;
LL a[maxn], dis[maxn];
LL dp[maxn];
void work() {
int n;
cin >> n;
for (int i = ; i <= n; ++i) cin >> a[i];
LL ans = ;
for (int i = ; i <= n - ; ++i) {
dis[i] = abs(a[i] - a[i + ]);
}
for (int i = ; i <= n - ; i += ) {
dis[i] = -dis[i];
}
for (int i = ; i <= n - ; ++i) {
dp[i] = max(dp[i - ] + dis[i], dis[i]);
ans = max(ans, dp[i]);
}
memset(dp, , sizeof dp);
for (int i = ; i <= n - ; i += ) {
dis[i] = -dis[i];
}
for (int i = ; i <= n - ; i += ) {
dis[i] = -dis[i];
}
for (int i = ; i <= n - ; ++i) {
dp[i] = max(dp[i - ] + dis[i], dis[i]);
ans = max(ans, dp[i]);
}
cout << ans << endl;
}int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}