MRSWAP - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given an array A of length 2N.
You can repeatedly choose i and swap A_i with A_{2N+1-i}.
Find the maximum possible value of A_1 + \ldots + A_N.

EXPLANATION:

For each 1 \le i \le N, observe that index i can only contain either the value A_i or the value A_{2N+1-i}.
This is because swapping A_i with A_{2N+1-i} twice will just bring A_i back to that position.

Since we’re aiming to maximize the sum, it’s optimal to just choose whichever is larger.

Thus, the answer is

\sum_{i=1}^N \max(A_i, A_{2N+1-i})

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    ans = 0
    for i in range(n):
        ans += max(a[i], a[2*n-1-i])
    print(ans)