Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define N 100005
- #define M 100005
- #define MOD 1000000007
- #define PI acos(-1)
- #define rep(i,a,b) for(int i = a; i < b; i++)
- #define reps(i,a,b) for(int i = a; i >= b; i--)
- #define sc scanf
- #define pc printf
- #define pb push_back
- #define F first
- #define S second
- const ll inf = -1e17;
- ll n,a[N],arr[N];
- ll maxCrossingSum(int l, int m, int h)
- {
- //cout << "yes" << endl;
- ll sum = 0;
- ll left_sum = arr[m];
- reps(i,m,l)
- {
- sum = sum + arr[i];
- if (sum > left_sum)
- left_sum = sum;
- }
- sum = 0;
- ll right_sum = arr[m+1];
- rep(i,m+1,h+1)
- {
- sum = sum + arr[i];
- if (sum > right_sum)
- right_sum = sum;
- }
- //cout << left_sum << " " << right_sum << endl;
- return left_sum + right_sum;
- }
- ll maxSubArraySum( int l, int h)
- {
- if(l > h) return inf;
- if (l == h)
- return arr[l];
- int m = (l + h)/2;
- //cout << l << " " << m << " " << h << endl;
- return max(maxSubArraySum(l, m),
- max(maxSubArraySum(m+1, h),
- maxCrossingSum(l, m, h)));
- }
- int main()
- {
- sc("%d",&n);
- rep(i,0,n) sc("%I64d",&a[i]);
- rep(i,0,n-1){
- arr[i] = abs(a[i] - a[i+1]);
- if(i % 2) arr[i] = -1*arr[i];
- }
- ll ans = maxSubArraySum(0,n-2);
- pc("%I64d\n",ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement