The numbers $1,2,\ldots,n$ are arranged into a circle. What is the maximum sum of the differences $|x_1-x_2|+|x_2-x_3|+\ldots+|x_{n-1}-x_n|+|x_n-x_1|$?
I think the maximum should occur when the numbers are arranged $n,1,n-1,2,n-2,3,\ldots$, but how to prove it formally?
The sum for this arrangement is $(n-1)+(n-2)+\ldots+1+\lfloor n/2\rfloor = \dfrac{n(n-1)}{2}+\lfloor n/2\rfloor$.
The key idea is that $|x - y|$ is basically either $x - y$ or $y - x$. Either way, one term (either $x$ or $y$) inside the absolute will be positive, and the other term will be negative.
This means, if you have $n$ absolutes, you will have $n$ positive terms and $n$ negative terms. Now, each $x_i$ appears twice in all of these absolutes, so in total we have $2n$ terms. So, since we must have $n$ positive terms and $n$ negative terms, in order to maximize the sum, we want to make the larger $x_i$s positive and the smaller $x_i$s negative.
I will demonstrate the case where $n$ is even (odd is similar, but need some little more work). By the argument in the previous paragraph, the sum cannot exceed:
$$2( (n/2+1) + (n/2+2) + \cdots + n) - 2 (1 + 2 + \cdots + n/2) = 2 \frac{n}{4} (\frac{n}{2} + 1 + n) - 2 \frac{n}{4} (1 + \frac{n}{2}) = n^2 / 2$$
Which matches your bound.