Given a sequence $a\_1, a\_2,\dots,a\_n$, define the two sequences
$$l\_i=\max\_{1 \leq j < i, a\_j \geq a\_i} j$$ 
or $0$ if it does not exist; and 
$$r\_i=\min\_{i < j \leq n, a\_j > a\_i} j$$ 
or $n+1$ if does not exist.


I want to find a permutation of $1, 2, ..., n$ so that 
$$\sum\_{1 \leq i \leq n} \min(i-l\_i,r\_i -i)$$ 
is maximized. How can this be done?



How to find a permutation of [n] so that $\sum\{\min(i-l[i],r[i]-i)\}$ is maximized?
Denote the maximum of your sum by $f(n)$, agree also that $f(0)=0$. If we fix $k$ such that $a\_k=n$, then the maximal possible value is $\min(k,n+1-k)+f(k-1)+f(n-k)$. So, we get a recursive formula $$f(n)=\max\_{1\leqslant k\leqslant (n+1)/2} k+f(k-1)+f(n-k).$$
Now we may forget about permutations and study this recurrence. Assume that $f(n)$ grows as $c(n+1)\ln(n+1)$ for some yet unknown $c$ and we try to prove that $f(n)\leqslant c(n+1)\ln(n+1)$ by induction (base $n=0$ is ok). Denote $k=\alpha(n+1)$, $\alpha\leqslant 1/2$, this reduces to $\alpha-cH(\alpha)\leqslant 0$ where $H(x)=-x\log(x)-(1-x)\log(1-x)$ is the entropy function. $H$ is concave, thus inequality $H(\alpha)\geqslant \alpha/c$ holds iff it holds for $\alpha=1/2$, $c=\frac1{2\log2}$, so $f(n)\leqslant (n+1)\log\_2(n+1)$ and we should insert the maximal value $n$ to the middle of the permutation (if you do so, you get almost equality.)


