Reverse-Operation-D&C

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long maxCrossingSum(vector<long long>& arr, int l, int m, int r) {
    long long sm = 0;
    long long left_sum = LLONG_MIN;

    for (int i = m; i >= l; i--) {
        sm = sm + arr[i];
        if (sm > left_sum) {
            left_sum = sm;
        }
    }

    sm = 0;
    long long right_sum = LLONG_MIN;
    for (int i = m; i <= r; i++) {
        sm = sm + arr[i];
        if (sm > right_sum) {
            right_sum = sm;
        }
    }

    return max(left_sum + right_sum - arr[m], max(left_sum, right_sum));
}

long long maxSubArraySum(vector<long long>& arr, int l, int r) {
    if (l > r) {
        return LLONG_MIN;
    }
    if (l == r) {
        return arr[l];
    }

    int m = (l + r) / 2;

    return max({maxSubArraySum(arr, l, m - 1), maxSubArraySum(arr, m + 1, r), maxCrossingSum(arr, l, m, r)});
}

long long reverse_operation(vector<long long>& arr, int n) {
    vector<long long> b_1, b_2;
    for (int i = 1; i < n; i += 2) {
        b_1.push_back(arr[i] - arr[i - 1]);
    }
    for (int i = 1; i < n - 1; i += 2) {
        b_2.push_back(arr[i] - arr[i + 1]);
    }

    long long change = max(maxSubArraySum(b_1, 0, b_1.size() - 1), maxSubArraySum(b_2, 0, b_2.size() - 1));
    long long even_sum = 0;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            even_sum += arr[i];
        }
    }

    return even_sum + max(0LL, change);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        cout << reverse_operation(arr, n) << endl;
    }
    return 0;
}