题意：给你一个数组，让你把连续的数分为一组，每一组的值为这一组数中的极差，问你这个怎样分组才能使得数组的极差和最大
解题思路：
可以分成 4种情况讨论
dp[i] 表示前 i+1项能得到的最大值
状态 状态转移方程
a[i-1] < a[i] < a[i+1] dp[i] = dp[i-1] + a[i+1] - a[i]
a[i-1] > a[i] < a[i+1] dp[i] = max(dp[i-1],dp[i-2] + a[i+1] -a[i])
a[i-1] > a[i] > a[i+1] dp[i] = dp[i-1] - a[i+1] + a[i]
a[i-1] < a[i] > a[i+1] dp[i] = max(dp[i-1],dp[i-2] - a[i+1] +a[i])
dp[n-1] 就是我们所求
解题代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 5 using namespace std; 6 7 typedef long long ll; 8 9 const int maxn=1000010; 10 11 ll dp[maxn]; 12 int a[maxn]; 13 14 int main() 15 { 16 int n;scanf("%d",&n); 17 for (int i=1;i<=n;i++) scanf("%d",&a[i]); 18 dp[0]=0; 19 for (int i=1;i<n;i++) 20 if (a[i+1]>=a[i]) 21 { 22 if ((i==1)||(a[i]>=a[i-1])) dp[i]=dp[i-1]+a[i+1]-a[i]; else dp[i]=max(dp[i-1],dp[i-2]+a[i+1]-a[i]); 23 } 24 else 25 { 26 if ((i==1)||(a[i]<a[i-1])) dp[i]=dp[i-1]-a[i+1]+a[i]; else dp[i]=max(dp[i-1],dp[i-2]-a[i+1]+a[i]); 27 } 28 cout<<dp[n-1]<<endl; 29 return 0; 30 }
from SanSiroWaltz
Codeforces 484(#276 Div 1) D Kindergarten DP
原文：http://www.cnblogs.com/zyue/p/4079043.html
