MAXADJSUM - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: raysh07
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

For an array B of length N, define f(B) = \sum_{i=1}^{N-1} (B_i + B_{i+1}).

You’re given an array A. Find the maximum possible value of f(A) if A can be rearranged as you please.

EXPLANATION:

Let’s rewrite f(A) a bit to bring it to a nicer form.

f(A) = \sum_{i=1}^{N-1} (A_i + A_{i+1}) \\ = (A_1 + A_2) + (A_2 + A_3) + (A_3 + A_4) + \ldots + (A_{N-1} + A_N) \\ = A_1 + (A_2 + A_2) + (A_3 + A_3) + \ldots + (A_{N-1} + A_{N-1}) + A_N \\ = A_1 + 2A_2 + 2A_3 + \ldots + 2A_{N-1} + A_N \\ = 2\cdot (A_1 + A_2 + \ldots + A_N) - A_1 - A_N

Here, notice that (A_1 + A_2 + \ldots + A_N) is just the sum of the array, and is constant irrespective of how it is rearranged.
So, if we let S = 2\cdot (A_1 + A_2 + \ldots + A_N), we have f(A) = S - A_1 - A_N, with the rearrangement only allowing us to choose the values of A_1 and A_N.

Since our aim is to maximize f(A), clearly it’s best to put the two smallest values in A at these positions.
That is, let m_1 and m_2 denote the smallest and second-smallest elements of A.
Then the answer is exactly

S - m_1 - m_2

Finding S, m_1, m_2 can all be done with a simple loop across the array.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    print(2*sum(a) - a[0] - a[1])