1373D.md (1669B)
1 Source: https://codeforces.com/problemset/problem/1373/D 2 3 D. Maximum Sum on Even Positions 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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). 22 23 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}$. 24 25 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). 26 27 You have to answer $t$ independent test cases. 28 29 Input 30 31 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. 32 33 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$. 34 35 It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$). 36 37 Output 38 39 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$. 40 41 Example 42 43 Input 44 45 ``` 46 4 47 8 48 1 7 3 4 7 6 2 9 49 5 50 1 2 1 2 1 51 10 52 7 8 4 5 7 6 8 9 7 3 53 4 54 3 1 2 1 55 ``` 56 57 Output 58 59 ``` 60 26 61 5 62 37 63 5 64 ```