fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Speed
  5. #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  6.  
  7. // Typedefs
  8. #define int long long
  9. #define pb push_back
  10. #define ff first
  11. #define ss second
  12. #define all(x) (x).begin(), (x).end()
  13. #define sz(x) ((int)(x).size())
  14. #define endl '\n'
  15.  
  16. void solve() {
  17.     int n;
  18.     cin >> n;
  19.     vector<int> a(n);
  20.     for (int &x : a) cin >> x;
  21.  
  22.     vector<int> pref(n + 1, 0);
  23.     for (int i = 0; i < n; i++) {
  24.         int val = (i % 2 == 0 ? a[i] : -a[i]);
  25.         pref[i + 1] = pref[i] + val;
  26.     }
  27.  
  28.     int total = pref[n];
  29.     int ans = LLONG_MIN;
  30.  
  31.     for (int k = 0; k < n; k++) {
  32.         int left = pref[k];
  33.         int right = total - pref[k + 1];
  34.         int cur = left - right;
  35.         ans = max(ans, cur);
  36.     }
  37.  
  38.     // flip pattern
  39.     for (int &x : a) x = -x;
  40.  
  41.     pref.assign(n + 1, 0);
  42.     for (int i = 0; i < n; i++) {
  43.         int val = (i % 2 == 0 ? a[i] : -a[i]);
  44.         pref[i + 1] = pref[i] + val;
  45.     }
  46.  
  47.     total = pref[n];
  48.     for (int k = 0; k < n; k++) {
  49.         int left = pref[k];
  50.         int right = total - pref[k + 1];
  51.         int cur = left - right;
  52.         ans = max(ans, cur);
  53.     }
  54.  
  55.     cout << ans << endl;
  56. }
  57.  
  58. int32_t main() {
  59.     fast_io;
  60.     int t;
  61.     cin >> t;
  62.     while (t--) solve();
  63.     return 0;
  64. }
  65.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
7
2
2 -3
4
1 4 3 4
4
-4 2 3 -6
5
-2 -3 4 10 -9
5
-12345678 -1000000000 -999999999 1000000000 -999999999
2
-7 1
5
7 -6 -1 -8 -8
stdout
copy 
3
5
13
20
2987654321
7
20
https://ideone.com/YslxLH
language:
C++ (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!