This is related to this question: Stack Overflow
Problem description
We are given a sequence of n positive integers. How to sort the elements to get the maximum combined sum of the differences between every two adjacent elements.
For example, for a sequence {8, 4, 1, 2, 3} the starting difference is (8-4) + (4-1) + (2-1) + (3-2) = 9, but 14 can be reached for {4, 8, 1, 3, 2}.
The best arrangement is {4, 1, 8, 2, 3}, sum 17.
Claim
Optimal solution can always be reached by either starting with the smallest or largest element and then alternately putting currently largest/smallest elements on both sides of the sequence.
That's not all yet: for the starting sequence {1, 2, 3, 4} we would start with 4 $\longrightarrow$ 1 4 2 $\longrightarrow$ 3 1 4 2 or 1 4 2 3. So this approach is not strict enough yet.
However, if we always first put to the left and then to the right (or otherwise), we are guaranteed that the number on the left side will be smaller/bigger than the corresponding number on the right side.
I tested the solution above so I am quite sure it works. I am interested how would you prove it.
You are correct:
When $n$ is even, the best arrangement has the highest and lowest in the middle, sandwiched between the second lowest and second highest, sandwiched between the third highest and third lowest, etc.
When $n$ is odd, the optimal arrangement either has the highest in the middle, sandwiched between the two lowest, then two remaining highest, etc, or it is the similar sequence where you start with the lowest in the middle.
The proof is easier when $n$ is even, so let's start there. Let the sequence of positive integers, sorted in increasing order, be $x_1\le x_2\le \dots\le x_n$. Then, for $i=1,\dots,n-1$, let $s_i=x_{i+1}-x_i$ be the sequence of gaps between the numbers. Finally, given a permutation $y_1,y_2,\dots,y_n$ of the given sequence, for $i=1,\dots,n-1$, let $$ m_i=\#\{j:y_{j}\le x_{i}\text{ and } y_{j+1}\ge x_{i+1}\}+\#\{j:y_j\ge x_{i+1}\text{ and } y_{j+1}\le x_i \} $$ In words, $m_i$ is the number of times the sequence $(y_1,\dots,y_n)$ crosses the "gap" between $x_i$ and $x_{i+1}$. Each time the sequence does this, it adds $s_i$ to the total of the absolute differences of the consecutive elements. Therefore, it follows that $$ |y_2-y_1|+|y_3-y_2|+\dots+|y_n-y_{n-1}|=\sum_{i=1}^{n-1}m_is_i $$ If this is unclear, I encourage you to look at some examples. You can then show two things:
For the proposed optimal sequence, we have$$ \begin{cases} m_i=2i & \text{when $i<n/2$}\\ m_{n/2}=n-1\\ m_{n-i}=2i & \text{when $i<n/2$}\\ \end{cases} $$
For any permutation, it is true that $$ \begin{cases} m_i\le 2i & \text{when $i<n/2$}\\ m_{n/2}\le n-1\\ m_{n-i}\le 2i & \text{when $i<n/2$}\\ \end{cases} $$
These two points imply that the proposed sequence is optimal.
The first bullet can be verified easily. For the second bullet, note that when $i<n/2$, that a crossing between $x_i$ and $x_{i+1}$ can only occur when one of the $i$ smallest values $x_1,\dots,x_i$ is next to one of the largest $n-i$ values. But this can obviously occur at most $2i$ times, to the left and right of each of the $i$ values $x_1,\dots,x_i$. The same logic applies to $m_{n-i}$. Finally, $m_{n/2}\le n-1$ since there are only $n-1$ adjacent pairs.
I leave the case when $n$ is odd to you. In this case, you will find three things:
When $i<n/2$, $m_i<2i$ and $m_{n-i}<2i$ (same as before).
Furthermore, letting $k=\lfloor n/2\rfloor$, it is impossible to have both $m_k=2k$ and $m_{k+1}=2k$. At least of these must be smaller than their maximal value in any permutation.
The two proposed optimal arrangements achieve the maximal values implied by the two previous bullet points.