Advertisement
Underdogs

Untitled

Mar 29th, 2017
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.42 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. #define N 100005
  7. #define M 100005
  8. #define MOD 1000000007
  9. #define PI acos(-1)
  10. #define rep(i,a,b) for(int i = a; i < b; i++)
  11. #define reps(i,a,b) for(int i = a; i >= b; i--)
  12. #define sc scanf
  13. #define pc printf
  14. #define pb push_back
  15. #define F first
  16. #define S second
  17.  
  18. const ll inf = -1e17;
  19.  
  20. ll n,a[N],arr[N];
  21.  
  22. ll maxCrossingSum(int l, int m, int h)
  23. {
  24. //cout << "yes" << endl;
  25.  
  26. ll sum = 0;
  27. ll left_sum = arr[m];
  28. reps(i,m,l)
  29. {
  30. sum = sum + arr[i];
  31. if (sum > left_sum)
  32. left_sum = sum;
  33. }
  34.  
  35.  
  36. sum = 0;
  37. ll right_sum = arr[m+1];
  38. rep(i,m+1,h+1)
  39. {
  40. sum = sum + arr[i];
  41. if (sum > right_sum)
  42. right_sum = sum;
  43. }
  44.  
  45. //cout << left_sum << " " << right_sum << endl;
  46. return left_sum + right_sum;
  47. }
  48.  
  49. ll maxSubArraySum( int l, int h)
  50. {
  51. if(l > h) return inf;
  52. if (l == h)
  53. return arr[l];
  54.  
  55. int m = (l + h)/2;
  56. //cout << l << " " << m << " " << h << endl;
  57.  
  58. return max(maxSubArraySum(l, m),
  59. max(maxSubArraySum(m+1, h),
  60. maxCrossingSum(l, m, h)));
  61. }
  62.  
  63.  
  64. int main()
  65. {
  66. sc("%d",&n);
  67. rep(i,0,n) sc("%I64d",&a[i]);
  68. rep(i,0,n-1){
  69. arr[i] = abs(a[i] - a[i+1]);
  70. if(i % 2) arr[i] = -1*arr[i];
  71. }
  72.  
  73.  
  74.  
  75. ll ans = maxSubArraySum(0,n-2);
  76.  
  77. pc("%I64d\n",ans);
  78.  
  79. return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement