Suppose $a_{k+1}-a_k=x_k$ for all $0\leq k\leq n$ and so we've $|x_k-x_{k-1}|\leq 1$ for all such $k$. Basically we need to show now $f_k=|x_k+x_{k-1}+.....+x_0|\leq \frac {k(n+1-k)}{2}$ for all such $k$. Now lets proceed by induction, (base case is not hard to show) suppose true up to $k-1$. Now fix a such $k$ numbers satisfying our hypothesis. Now note maximum value of $|x+a|$ occurs at $x=t$ or $-t$ if it's given $a$ is fixed and $-t\leq x\leq t$. Now we've to take $x_k$ such as $|x_k-a|\leq 1$ where call $a=x_{k-1},c=x_{k-2}+x_{k-3}+.....+x_0$. Now so maximum value of $f_k$ is either $|1+c|$ or $|2a+c-1|$. Basically hard part is with $|c+1|$. So do first with other one, suppose $|2a+c-1|\geq |1+c|\implies (a+1)(a-c)\geq 0$. Now actually there is no problem taking $a,c\geq 0$ , since as $x_i$'s are real so, we can multiply each of them with $-1$. Now so we must have $a+1\geq 0\implies f_k\leq 2a+c$. Now just by triangle inequality we get $a\leq k+|a_1|\leq k+1$ and also $c\leq \frac {(k-2)(n+3-k)}{2}$. Now $2a+c\leq 3a\leq 3k+3 \leq \frac{k(n+1-k)}{2}\implies k\leq \frac{n+3}{2}$ ,similarly, if maximum would be $|c+1|$ then we would have to show $\frac {(k-2)(n+3-k)}{2}\leq \frac{k(n+1-k)}{2}\implies k\leq \frac{n+3}{2}$. So for all $k \leq \frac{n+3}{2}$ we're done.To proceed further, if $k>\frac{n+3}{2}$ then using, $x_0+x_1+x_2+.....+x_{n+1}=0$ we would get another $l\leq \frac{n+3}{2}$ numbers holding same property, so again we're done similarly as previous.

Click to reveal hidden text

substitute $a_{k-1}-a_{k}=b_{k-1}$ we have the following two identities: \[-a_k=\sum_{i=0}^{k-1}(i+1)(b_{i}-b_{i+1})+kb_{k}\] and \[a_{k}=\sum_{i=k}^{n-1}(b_{i+1}-b_{i})(n-i)+(n-k+1)b_{k}\] we have \[|ka_{k}+(n-k+1)a_{k}|\] \[=|k[\sum_{i=k}^{n-1}(b_{i+1}-b_{i})(n-i)]-(n-k+1)[\sum_{i=0}^{k-1}(i+1)(b_{i}-b_{i+1})]|\] \[\le k[1+2+\dots+n-k]+(n-k+1)[1+2+\dots+k]=\frac{k(n-k+1)(n+1)}{2}\]