India — Team Selection Test, 2007

Minimum: Consider $1$ and $n$ on the circle. They divide the circle into two arcs. The sum of the numbers on either of the arc is at least $n-1$. Suppose for example the numbers $1 = b_1, b_2, \dots, b_k = n$ appear on one of the arcs between $1$ and $n$, in that order. Then the sum of absolute differences of adjacent numbers on this arc is
$$|1 - b_2| + |b_2 - b_3| + \dots + |b_{k-1} - n| \geq |1 - n| = n - 1.$$
Similarly, the least sum of absolute differences on the other arc is also $n-1$. Hence we see that
$$\sum_{j=1}^{n} |a_{j+1} - a_{j}| \geq 2(n-1).$$
This is achieved by the permutation $(a_1, a_2, \dots, a_n)$, where $a_j = j$ for $1 \le j \le n$.

Maximum: We have
$$\sum_{j=1}^{n} |a_{j+1} - a_{j}| = \sum_{j=1}^{n} \pm (a_{j+1} - a_{j}).$$
Each of the numbers $1, 2, \dots, n$ appear in the right side sum twice. Hence to get a maximum sum we should have positive sign to larger numbers in both occurrences and smaller number should go with negative sign. Thus $n, (n-1), (n-2), \dots, [n/2]$ should get positive signs and $1, 2, 3, \dots, [n/2] - 1$ should get negative signs. This happens when:
for even $n$, the arrangement is $1, n, 2, (n-1), 3, (n-2), \dots, n/2, (n/2) + 1$;
for odd $n$, the arrangement is $1, n, 2, (n-1), 3, (n-2), \dots, [n/2] + 2, [n/2] + 1$.
The corresponding sums are:
$$\frac{n^2}{2} \text{ when } n \text{ is even, } \quad \frac{n^2-1}{2} \text{ when } n \text{ is odd.}$$