2274B.md (1840B)
1 Source: https://codeforces.com/problemset/problem/2274/B 2 3 B. Prefix 4 5 time limit per test 6 7 1 second 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_1, a_2, \ldots, a_n$. 22 23 For each index $i = 2, 3, \ldots, n$ in order, perform the following: 24 25 * Define $s = a_1 + a_2 + \ldots + a_{i-1}$. 26 * Replace $a_i$ with one of the following three values: $a_i - s$, $a_i$, or $a_i + s$. 27 28 Over all possible choices, find the maximum value of $\max(a_1, a_2, \ldots, a_n)$ after the process described above. 29 30 Input 31 32 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 33 34 The first line of each test case contains a single integer $n$ ($2 \le n \le 50$). 35 36 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-50 \le a_i \le 50$). 37 38 Output 39 40 For each test case, output a single integer — the maximum achievable value of $\max(a_1, a_2, \ldots, a_n)$. 41 42 Please note that the answer for some test cases won't fit into a 32-bit integer type, so you should use at least a 64-bit integer type in your programming language (like long long in C++). 43 44 Example 45 46 Input 47 48 ``` 49 4 50 51 5 52 53 3 -5 1 -4 2 54 55 2 56 57 -1 2 58 59 3 60 61 1 2 3 62 63 3 64 65 -2 -2 -2 66 ``` 67 68 Output 69 70 ``` 71 24 72 73 3 74 75 7 76 77 4 78 ``` 79 80 Note 81 82 In the first test case, the final array can be made $[3, -8, -4, -13, 24]$, so the answer is $24$. 83 84 In the second test case, for $i = 2$, $s = a_1 = -1$. Replacing $a_2$ with $a_2 - s = 2 - (-1) = 3$ gives the answer $3$. 85 86 In the third test case, the final array can be made $[1, 3, 7]$, so the answer is $7$. 87 88 In the fourth test case, replacing $a_2$ with $a_2 + s = -4$ makes $s = -6$ for $i = 3$. Replacing $a_3$ with $a_3 - s = -2 - (-6) = 4$ gives the final array $[-2, -4, 4]$, so the answer is $4$.