Code

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

long long solve(vector<long long> &a) {
    int n = a.size();

    vector<long long> suffix_sum = a;
    for (int i = n - 2; i >= 0; i--) {
        suffix_sum[i] += suffix_sum[i + 1];
    }

    vector<long long> dp(n, 0);
    // dp[i] is the answer for a[i ... ]

    dp[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        // Cut alone.
        auto cut_alone = a[i] + dp[i + 1] + suffix_sum[i + 1];

        // Cut with the group.
        auto cut_with_group = a[i] + dp[i + 1];

        dp[i] = max(cut_alone, cut_with_group);
    }

    return dp[0];
}

int main() {
    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cout << solve(a) << "\n";
    }
    return 0;
}