1899C - Yarik and Array - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define dbg(...) 42

#endif
#define pi 3.141592653589793238
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define int long long

ll M = 1000000007;
ll M2 = 998244353;
// Solution Start Here.....n
int par(int n)
{
    n = abs(n);
    return n % 2;
}
void solve()
{
    int n;
    cin >> n;
    int a[n];
    cin >> a[0];
    int mx = a[0];
    vector<int> sum(n, 0);
    for (int i = 1; i < n; i++)
    {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    sum[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--)
    {
        if (par(a[i]) != par(a[i + 1]))
            sum[i] = max(sum[i + 1] + a[i], a[i]);
        else
            sum[i] = a[i];
        mx = max(mx, sum[i]);
    }
    cout << mx << "\n";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1;
    cin >> TET;
    for (int i = 1; i <= TET; i++)
    {

        solve();
#ifndef ONLINE_JUDGE
        cout << "__________________________" << endl;
#endif
    }
#ifndef ONLINE_JUDGE
    cerr << endl
         << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}