2062C.md (1705B)
1 Source: https://codeforces.com/problemset/problem/2062/C 2 3 C. Cirno and Operations 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Cirno has a sequence $a$ of length $n$. She can perform either of the following two operations for any (possibly, zero) times unless the current length of $a$ is $1$: 22 23 * Reverse the sequence. Formally, $[a_1,a_2,\ldots,a_n]$ becomes $[a_n,a_{n-1},\ldots,a_1]$ after the operation. 24 * Replace the sequence with its difference sequence. Formally, $[a_1,a_2,\ldots,a_n]$ becomes $[a_2-a_1,a_3-a_2,\ldots,a_n-a_{n-1}]$ after the operation. 25 26 Find the maximum possible sum of elements of $a$ after all operations. 27 28 Input 29 30 The first line of input contains a single integer $t$ ($1 \leq t \leq 100$) — the number of input test cases. 31 32 The first line of each test case contains a single integer $n$ ($1\le n\le 50$) — the length of sequence $a$. 33 34 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($|a_i|\le 1000$) — the sequence $a$. 35 36 Output 37 38 For each test case, print an integer representing the maximum possible sum. 39 40 Example 41 42 Input 43 44 ``` 45 5 46 47 1 48 49 -1000 50 51 2 52 53 5 -3 54 55 2 56 57 1000 1 58 59 9 60 61 9 7 9 -9 9 -8 7 -8 9 62 63 11 64 65 678 201 340 444 453 922 128 987 127 752 0 66 ``` 67 68 Output 69 70 ``` 71 -1000 72 8 73 1001 74 2056 75 269891 76 ``` 77 78 Note 79 80 In the first test case, Cirno can not perform any operation, so the answer is $-1000$. 81 82 In the second test case, Cirno firstly reverses the sequence, then replaces the sequence with its difference sequence: $[5,-3]\to[-3,5]\to[8]$. It can be proven that this maximizes the sum, so the answer is $8$. 83 84 In the third test case, Cirno can choose not to operate, so the answer is $1001$.