Maximize $\ S=Max{(\sum_{i=1}^{n-1} |f(i+1)-f(i)|)}$

Question

Let $\ f: \{1,2,...n\} → \{1,2,...n\} \quad bijection$

What I want to know is

$\ S=Max{(\sum_{i=1}^{n-1} |f(i+1)-f(i)|)}$

Furthermore, Is there a way to know 'when' does S would be maximized?

I could find the solution as [n^2/2]-1 and method for every n but hard to prove that it is maximum.

Answer 1

Using the triangle inequality, we have, with $\mu=\frac{n+1}2$,

\begin{align} \sum_{i=1}^{n-1}\left|\,f(i+1)-f(i)\right| &\le \sum_{i=1}^{n-1}\left(\left|\,f(i+1)-\mu\right|+\left|\,f(i)-\mu\right|\right) \\ &=2\sum_{k=1}^n\left|k-\mu\right|-|\,f(1)-\mu|-|\,f(n)-\mu| \\ &=\left\lfloor\frac{n^2}2\right\rfloor-|\,f(1)-\mu|-|\,f(n)-\mu| \\ &\le\left\lfloor\frac{n^2}2\right\rfloor-1\;. \end{align}

Equality holds if all neighbouring pairs are on opposite sides of $\mu$ and $f(1)$ and $f(n)$ are $\lfloor\mu\rfloor$ and $\lceil\mu\rceil$. Since we have the same number of elements on either side of $\mu$, this is possible; see OEIS entry A047838 for one concrete arrangement.

Answer 2

I found another way to get upper bound.

$\sum_{i=1}^{n-1} |f(i+1)-f(i)|= ±1±1±2±2 ...±n±n$ $≤-1-1-2-2...+(n-1)+(n-1)+n+n) =⌊{n^2}/{2}⌋−1$

$'±'$ means choosing $'+'$or $'-' $

so we can get upper bound $⌊{n^2}/{2}⌋−1$