codeforces-789C【分类+简单递推】

1 #include

2 #define rep(i,a,b) for(int i = a;i <= b;++ i) 3 #define per(i,a,b) for(int i = a;i >= b;-- i)

4 #define mem(a,b) memset((a),(b),sizeof((a))) 5 #define FIN freopen(\"in.txt\

6 #define IO ios_base::sync_with_stdio(0),cin.tie(0) 7 #define pb push_back 8 #define mid ((l+r)>>1) 9 #define ls (id<<1)10 #define rs ((id<<1)|1)11 using namespace std;12 typedef long long LL;

13 typedef pair PIR;14 const int N = 1e5+5;15

16 int n;

17 LL a[N], sum1[N], sum2[N];18

19 int main()20 {IO;

21 //FIN;22 cin >> n;

23 rep(i, 1, n) cin >> a[i];

24 rep(i, 1, n-1) sum1[i] = sum1[i-1]+abs(a[i+1]-a[i])*((i-1)&1?-1:1);25 rep(i, 1, n-1) sum2[i] = sum2[i-1]+abs(a[i+1]-a[i])*((i-1)&1?1:-1);26 LL ans = -1e9, minn = 1e9;27 rep(i, 1, n-1){

28 ans = max(ans, max(sum1[i], sum1[i]-minn));29 minn = min(minn, sum1[i]);30 }

31 minn = 1e9;32 rep(i, 1, n-1){

33 ans = max(ans, max(sum2[i], sum2[i]-minn));34 minn = min(minn, sum2[i]);35 }

36 cout << ans << endl;37 return 0;38 }

View Code