fork download
copy 
  1. #include <algorithm>
  2. #include <iomanip>
  3. #include <iostream>
  4. #include <vector>
  5. #include <set>
  6. #include <numeric>
  7. #include <map>
  8. #include <unordered_map>
  9. using namespace std;
  10. #define all(a) a.begin(), a.end()
  11. #define ll long long
  12. #define fo(i,n) for (long long i = 0; i < n; i++)
  13. int main()
  14. {
  15.     ll i,a,b,c;
  16.     ios_base::sync_with_stdio(false);
  17.  
  18.     ll input;
  19.     cin.tie(0); cout.tie(0);
  20.     cin >> i;
  21.     while (i--)
  22.     {
  23.         cin >> a;
  24.         vector<ll> nums(a);
  25.         vector<ll> prefix(a);
  26.         fo(j,a)
  27.         {
  28.             cin >> input;
  29.             nums[j] = input;
  30.             if (j == 0)
  31.             {
  32.                 prefix[j] = abs(nums[j]);
  33.             }
  34.             else
  35.             {
  36.                 prefix[j] = prefix[j-1] + abs(nums[j]);
  37.             }
  38.         }
  39.         ll sum = 0;
  40.         ll left = 0;
  41.         ll right = a-1;
  42.         for (int j = 0; j < a; j++)
  43.         {
  44.             if (nums[j] >= 0)
  45.             {
  46.                 sum+= nums[j];
  47.                 left++;
  48.             }
  49.             else
  50.             {
  51.                 break;
  52.             }
  53.         }
  54.         for (int j = a-1; j >= 0; j--)
  55.         {
  56.             if (nums[j] < 0)
  57.             {
  58.                 sum+= -1*(nums[j]);
  59.                 right--;
  60.             }
  61.             else
  62.             {
  63.                 break;
  64.             }
  65.         }
  66.         int plussum = 0;
  67.         int minsum = 0;
  68.         for (int j = left; j <= right; j++)
  69.         {
  70.             if (nums[j] >= 0)
  71.             {
  72.                 plussum+= nums[j];
  73.             }
  74.             else
  75.             {
  76.                 minsum+= nums[j];
  77.             }
  78.         }
  79.         ll negsum = 0;
  80.         ll addsum = 0;
  81.         ll possum = 0;
  82.         for (int j = left; j <= right; j++)
  83.         {
  84.             if (nums[j] < 0)
  85.             {
  86.                 negsum+= -nums[j];
  87.             }
  88.             else
  89.             {
  90.                 if (nums[j] > negsum)
  91.                 {
  92.                     addsum += nums[j];
  93.                     negsum = 0;
  94.                 }
  95.             }
  96.         }
  97.         for (int j = right; j >= left; j--)
  98.         {
  99.             if (nums[j] >= 0)
  100.             {
  101.                 possum += nums[j];
  102.             }
  103.             else
  104.             {
  105.                 if (-nums[j] > possum)
  106.                 {
  107.                     addsum += -nums[j];
  108.                     possum = 0;
  109.                 }
  110.             }
  111.         }
  112.         cout << max(addsum,sum + max(plussum,-1*(minsum))) << '\n';
  113.     }
  114. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
1
15
-19 -16 -6 5 -9 -14 16 18 16 6 6 -14 -18 -8 13
stdout
copy 
104
https://ideone.com/fsBS7o
language:
C++14 (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!