题目链接：http://codeforces.com/problemset/problem/789/C
题目大意：对于N个数，选定其中的【L,R】的数， 使得|a[l+1]-a[l]|-|a[l+2]-a[l+3]|+….+|a[r-1]-a[r-2]|-|a[r]-a[r-1]|最大； 其实就是每两个数做差，得到一个n-1长度的序列b，然后对序列b的【L,R】区间里，从L开始数第一项以及后面的奇数项都是加，第二项以及后面的偶数项都是减。在这样的条件下求出最大值。
思路：分成两种情况，对于新构造的序列b，一种是选择的区间里，L是奇数，另一种就是L是偶数了。 不难看出，如果选择的L是奇数，那么在进行累加的时候，偶数项都应该是减掉，也就是只要对序列b的偶数项都乘上一个-1之后，用一维DP的思路求最大连续子序列和（Max Sum ,详情参考hdu1003），得出一个最大值，然后把奇数项乘上-1，偶数项变回原状，再求一次Max Sum，取两者之间的较大值即可。
简单说下hdu1003，也就是最大连续子序列和； 用dp的思路将，dp【i】应该是保存【1，i】这个区间里，以i为结尾的最大连续子序列和； 而对于dp【i+1】来说，如果dp【i】>0，那么dp[i+1]=dp[i]+a[i+1];否则，dp[i+1]=a[i+1]；因为前缀比0小，加上反而会变少。然后可以发现，每次DP的过程，并不需要用到之前的dp[i-2]的数据，所以连数组都不用开，直接用一个变量sum记录一个累加和，一旦sum小于0就从0开始继续累加就好。
注意：数据爆int，需要longlong
AC代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; inline LL absi(LL n) { if(n<0) return -n; return n; } LL road[100005]; int main() { int n; cin>>n; for(int i=0 ; i<n ; i++) { cin>>road[i]; } LL maxi=0; LL save=0; for(int i=1 ; i<n ; i++) { road[i-1]=absi(road[i-1]-road[i]); maxi=max(road[i-1],maxi); } for(int i=0 ; i<n-1 ; i++) { if(i%2!=0) road[i]*=-1; } for(int i=0 ; i<n-1 ; i++) { save+=road[i]; if(save<0) { save=0; } maxi=max(maxi,save); } for(int i=0 ; i<n-1 ; i++) { road[i]*=-1; } save=0; for(int i=0 ; i<n-1 ; i++) { save+=road[i]; if(save<0) { save=0; } maxi=max(maxi,save); } cout<<maxi<<endl; return 0; }