Greedy algorithm correctness proof for "Elegant Permuted Sum" (UVa 11158)
This algorithm appears and is analyzed in Curtis, Darts and hoopla board design. Curtis actually considers two problems:


Dartboard design: Given a sequence of numbers, find a circular arrangement $a_1,\ldots,a_n$ maximizing $\sum_{i=1}^n |a_i-a_{i+1}|^q$ for some $q \geq 1$ (where $a_{n+1} = a_1$).
Hoopla board design: Given a sequence of numbers, find a permutation $a_1,\ldots,a_n$ maximizing $\sum_{i=1}^{n-1} |a_i-a_{i+1}|^q$ for some $q \geq 1$.


Your problem is the hoopla board design with $q = 1$. You can find a complete proof of the greedy algorithm in Curtis' paper. It's not trivial, though also not too complicated.