Advertisement
Josif_tepe

Untitled

May 28th, 2024
572
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF = 2e9;
  4. int main()
  5. {
  6.    int n;
  7.    cin >> n;
  8.  
  9.    vector<int> v(n);
  10.    vector<int> dp1(n + 1), dp2(n + 1), dp3(n + 1), dp4(n + 1);
  11.    for(int i = 0; i < n; i++) {
  12.     cin >> v[i];
  13.    }
  14.    for(int i = 0; i < n; i++) {
  15.     dp1[i] = -INF;
  16.     dp2[i] = -INF;
  17.     dp3[i] = -INF;
  18.     dp4[i] = -INF;
  19.    }
  20.    for(int i = n - 1; i >= 0; i--) {
  21.     dp1[i] = max(dp1[i + 1], v[i]);
  22.    }
  23.    for(int i = n - 2; i >= 0; i--) {
  24.     dp2[i] = max(dp2[i + 1], dp1[i + 1] - v[i]);
  25.    }
  26.    for(int i = n - 3; i >= 0; i--) {
  27.     dp3[i] = max(dp3[i + 1], dp2[i + 1] + v[i]);
  28.    }
  29.    for(int i = n - 4; i >= 0; i--) {
  30.     dp4[i] = max(dp4[i + 1], dp3[i + 1] - v[i]);
  31.    }
  32.    int res = -INF;
  33.    for(int i = 0; i <= n; i++) {
  34.     res = max(res, dp4[i]);
  35.    }
  36.    cout << res << endl;
  37.  
  38.     return 0;
  39. }
  40.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement