Find the maximun of the sum $\sum_{k=1}^{n}(f(f(k))-f(k))$ Let $f:\{1,2,3,\cdots,n\}\to \{1,2,3,\cdots,n\}$ such that
$$f(1)\le f(2)\le\cdots\le f(n)$$
Let $g(n)$
$$g(n)=max\left(\sum_{k=1}^{n}(f(f(k))-f(k))\right)$$
Find $$g(n)$$
 A: My best effort:
Let $m=\lceil \frac{n+1}{2}\rceil$. So $m=\frac{n+1}{2}$ for odd $n$, and $m=\frac{n+2}{2}$ for even $n$.
Then let $f(k)=m$ for $1 \le k \lt m$ and $f(k)=n$ for $m \le k \le n$. In particular $f(m)=f(n)=n$.
In this case $f(f(k))=n$ for all $k$ and so $\displaystyle \sum_{k=1}^n (f(f(k))-f(k)) = (m-1)(n-m).$
For odd $n$ this gives $\displaystyle \sum_{k=1}^n (f(f(k))-f(k)) = \left(\frac{n=1}{2}\right)^2 = \frac{n^2}{4}-\frac{n}{2}+\frac14.$
For even $n$ this gives $\displaystyle \sum_{k=1}^n (f(f(k))-f(k)) = \frac{n}{2}   \times \frac{n-2}{2}= \frac{n^2}{4}-\frac{n}{2}.$
A: This is not a proof but I presume this may be the maximum.
Assume
$$f(k)=\min (k+d,n)\quad(d\ge1)$$
Then
\begin{align}
&\sum_{k=1}^n (f(f(k))-f(k))\\
&=\sum_{k=1}^n f(f(k))-\sum_{k=1}^nf(k)\\
&=\sum_{k=1}^n f(\min (k+d,n))-\sum_{k=1}^n\min (k+d,n))\\
&=\sum_{k=1}^n \min(\min (k+d,n)+d,n)-\sum_{k=1}^n\min (k+d,n))\\
&=\sum_{k=1}^{n-d} \min(k+2d,n)+\sum_{k=n-d+1}^{n}\min(n+d,n)-\sum_{k=1}^{n-d} (k+d)-\sum_{k=n-d+1}^{n}n\\
&=\sum_{k=1}^{n-2d} (k+2d)+\sum_{k=n-2d+1}^{n} n-\sum_{k=1}^{n-d} (k+d)-\sum_{k=n-d+1}^{n}n\\
&=\sum_{k=1}^{n-2d} d+\sum_{k=n-2d+1}^{n-d}(n-(k+d))\\
&=(n-2d)d+d(n-d)-\sum_{k=1}^{n-d}k+\sum_{k=1}^{n-2d+1}k\\
&=2nd-3d^2-\frac{(n-d)(n-d+1)}2+\frac{(n-2d)(n-2d+1)}2\\
&=\frac{(2n-1)d-3d^2}{2}\\
&=\frac{-3\left(d-\left(\frac{2n-1}{6}\right)\right)^2+3\left(\frac{2n-1}{6}\right)^2}{2}\\
&\le \frac{(2n-1)\lfloor\frac{2n-1}{6}\rfloor-3\lfloor\frac{2n-1}{6}\rfloor^2}{2}
\end{align}
