We will assume that n is odd. The case where n is even is similar and simpler.

Suppose that in the optimal permutation there are three consecutive elements a, b, c in increasing order, ie. a < b < c. It is easy to see that swapping b and c will not decrease the answer. The same applies for three consecutive elements in decreasing order. Therefore, given an optimal permutation, we can scan from left to right and whenever we find three monotonic elements, we may swap the latter two. This operation can not decrease the score and at the end, there will be no three monotonic elements. That means, in the optimal permutation, either all even indexed elements are larger than their neighbors or all even indexed elements are smaller than their neighbors.

Suppose that all even indexed elements are larger than their neighbors. Let bi = api. Then the score can be written as $\sum_{i=1}^{n-1} |b_i - b_{i+1}| = (b_2-b_1) + (b_2 - b_3) + \cdots + (b_{n-1}-b_{n-2}) + b_{n-1} - b_n) = 2b_2 + 2b_4 + \cdots + 2b_{n-1} - (b_1 + 2b_3 + \cdots + 2b_{n-2} + b_n $. In other words, contribution of all even positions are +2 and all odd positions except 1 and n is -2. 1 and n has contribution -1. To maximize the score, we should place the $\lfloor{n\over2} \rfloor $ largest elements in the even positions, the next two largest in positions 1 and n and rest in the remaining odd positions.

The case where all even indexed elements are smaller than their neighbors is similar. There to maximize the score, we should place the $\lfloor{n\over2} \rfloor $ smallest elements in the even positions, the next two smallest in positions 1 and n and rest in the remaining odd positions. We should take the maximum out of the two cases.

Statistics

37% Solution Ratio
dontquitEarliest, Mar '20
mumith_fahim99Fastest, 0.0s
EgorKulikovLightest, 3.7 MB
rummanrakib11Shortest, 942B
Toph uses cookies. By continuing you agree to our Cookie Policy.