Maximum Sum on Even Positions
Contest: Educational Codeforces Round 90 (Rated for Div. 2)
Difficulty rating: 1600
Tags: divide and conquer, dp, greedy, implementation

You are given an array $$$a$$$ consisting of $$$n$$$ integers. Indices of the array start from zero (i. e. the first element is $$$a_0$$$, the second one is $$$a_1$$$, and so on).

You can reverse at most one subarray (continuous subsegment) of this array. Recall that the subarray of $$$a$$$ with borders $$$l$$$ and $$$r$$$ is $$$a[l; r] = a_l, a_{l + 1}, \dots, a_{r}$$$.

Your task is to reverse such a subarray that the sum of elements on even positions of the resulting array is maximized (i. e. the sum of elements $$$a_0, a_2, \dots, a_{2k}$$$ for integer $$$k = \lfloor\frac{n-1}{2}\rfloor$$$ should be maximum possible).

You have to answer $$$t$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of $$$a$$$. The second line of the test case contains $$$n$$$ integers $$$a_0, a_1, \dots, a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output format:
For each test case, print the answer on the separate line — the maximum possible sum of elements on even positions after reversing at most one subarray (continuous subsegment) of $$$a$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4
8
1 7 3 4 7 6 2 9
5
1 2 1 2 1
10
7 8 4 5 7 6 8 9 7 3
4
3 1 2 1

Example output:
26
5
37
5

Editorial:
Firstly, we can notice that the reverse of of odd length subarray does nothing because it doesn't change parities of indices of affected elements. Secondly, we can consider the reverse of the subarray of length $$$2x$$$ as $$$x$$$ reverses of subarrays of length $$$2$$$ (i.e. it doesn't matter for us how exactly the subarray will be reversed, we can only consider changing parities).
Now, there are two ways: the first one is smart and the second one is dynamic programming.
Consider the first way. Calculate the initial sum of elements on even positions $$$sum$$$. Then let's create two arrays $$$v_1$$$ and $$$v_2$$$. There $$$v_1[i]$$$ is $$$a[2i+1] - a[2i]$$$ for all $$$i$$$ from $$$0$$$ to $$$\lfloor\frac{n}{2}\rfloor - 1$$$ and $$$v_2[i]$$$ is $$$a[2i] - a[2i+1]$$$ for all $$$i$$$ from $$$0$$$ to $$$\lfloor\frac{n}{2}\rfloor - 1$$$. Elements of the first array deonte the profit if we reverse the subarray tarting from the even position, and elemnts of the second array denote the profit if we reverse the subarray starting from the odd position. Now we need to find the subarray with the maximum sum in both arrays (this will maximize overall profit) and add this value to $$$sum$$$ to get the answer. This problem can be solved easily: consider the sum of the subarray $$$[l; r]$$$ as the difference of two prefix sums $$$pref_{r} - pref_{l-1}$$$. To maximize it, consider all right borders and minimize the value $$$pref_{l-1}$$$. Iterate over all positions of the array, maintaining the current prefix sum $$$csum$$$ and the minimum prefix sum we meet $$$msum$$$. Update $$$csum := csum + a_i$$$, then update $$$msum := min(msum, csum)$$$ and then update the answer with the value $$$csum - msum$$$.
And the second way is author's solution and it is dynamic programming. This idea can be transformed to solve such problems in which you need to apply some function to some small number of subsegments (of course, under some constraints on functions). State of our dynamic programming is $$$dp_{i, j}$$$ where $$$i \in [0; n]$$$ and $$$j \in [0; 2]$$$. $$$dp_{i, 0}$$$ denotes the answer on the prefix of length $$$i$$$ if we didn't start reversing the subarray, $$$dp_{i, 1}$$$ denotes the answer if we started reversing the subarray but didn't end it and $$$dp_{i, 2}$$$ denotes the answer if we ended reversing the subarray. Transitions are pretty easy:
• $$$dp_{i + 1, 0} = max(dp_{i + 1, 0}, dp_{i, 0} + [i \% 2 == 0? a_i : 0])$$$;
• $$$dp_{i + 2, 1} = max(dp_{i + 2, 1}, max(dp_{i, 0}, dp_{i, 1}) + [i \% 2 == 0 ? a_{i + 1} : a_i])$$$;
• $$$dp_{i + 1, 2} = max(dp_{i + 1, 2}, max(dp_{i, 0}, dp_{i, 1}, dp_{i, 2}) + [i \% 2 == 0? a_i : 0])$$$.
The value $$$x ? y : z$$$ is just a ternary if statement. If $$$x$$$ is true then return $$$y$$$ otherwise return $$$z$$$.
The answer is $$$max(dp_{n, 0}, dp_{n, 1}, dp_{n, 2})$$$.
Time complexity with both approaches is $$$O(n)$$$.