http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1270
简单的线性dp，最近狂刷水题真的是。。。药丸
差值最大得话要么是峰顶要么是最小的1，不可能处在中间状态，那样显然没有峰值的贡献大，想通这一点之后方程就好写了，
dp[i][0]表示第i个数取最小值的最大代价，dp[i][1]相反。
有 dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i-1]-1);
dp[i][1]=max(dp[i-1][0]+a[i]-1,dp[i-1][1]+abs(a[i]-a[i-1]);
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define inf 0x3f3f3f3f
LL mod=1e9+;
LL dp[][];
int a[];
int main()
{
int N,i,j;
cin>>N;
for(i=;i<=N;++i) scanf("%d",a+i);
dp[][]=a[]-;
dp[][]=a[]-;
for(i=;i<=N;++i)
{
dp[i][]=max(dp[i-][],dp[i-][]+a[i-]-);
dp[i][]=max(dp[i-][]+a[i]-,dp[i-][]+abs(a[i]-a[i-]));
}
cout<<max(dp[N][],dp[N][])<<endl;
return ;
}