反着求一遍最大连续子序列(前项依赖)
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 const int MAXN = 200005; 5 int n; 6 LL dp[MAXN]; 7 LL a[MAXN]; 8 LL Cal(int i) 9 { 10 return abs(a[i] - a[i+1]); 11 } 12 int main() 13 { 14 scanf("%d", &n); 15 for (int i = 1; i <= n; i++) 16 scanf("%lld", &a[i]); 17 memset(dp, 0, sizeof(dp)); 18 dp[n-1] = Cal(n-1); 19 LL ans = dp[n-1]; 20 for (int i = n-2; i > 0; i--) 21 { 22 dp[i] = max(Cal(i), Cal(i) - dp[i+1]); 23 if (i < n-2) 24 dp[i] = max(dp[i], dp[i+2] - Cal(i+1) + Cal(i) ); 25 ans = max(dp[i], ans); 26 } 27 printf("%lld ", ans); 28 }