题意：
给你n个连续的数，让你划分成连续的区间，每个区间的价值为此区间内最大最小值之差，问你这n个数形成的最大价值是多少
思路：
最终的被分出来的序列都应该是单调的，如果你是形如 4 6 1 的，很可能可以将4或者1分割出去得到更大的值
贪心是让一段序列的元素少，这样构成的序列更多，获得的值也就可能越大。
考虑v形倒v形就好了
代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define mem(a) memset(a,0,sizeof(a)) 5 #define mp(x,y) make_pair(x,y) 6 const int maxn = 1e6+10; 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 17 ll a[maxn],dp[maxn]; 18 19 int main(){ 20 int n=read(); 21 for(int i=1; i<=n; i++) 22 a[i] = read(); 23 mem(dp); 24 for(int i=2; i<=n; i++){ 25 if(a[i-1]>a[i] && a[i-1]>a[i-2]) dp[i] = max(dp[i-1],dp[i-2]+a[i-1]-a[i]); 26 if(a[i-1]<a[i] && a[i-1]<a[i-2]) dp[i] = max(dp[i-1],dp[i-2]+a[i]-a[i-1]); 27 if(a[i]>=a[i-1] && a[i-1]>=a[i-2]) dp[i] = dp[i-1] + a[i]-a[i-1]; 28 if(a[i]<=a[i-1] && a[i-1]<=a[i-2]) dp[i] = dp[i-1] + a[i-1]-a[i]; 29 } 30 // for(int i=1; i<=n; i++) 31 // cout << dp[i] << " "; 32 // cout << endl; 33 34 cout << dp[n] << endl; 35 36 return 0; 37 }