# How to find a permutation of [n] so that $\sum\{\min(i-l[i],r[i]-i)\}$ is maximized?

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?

## 1 Answer

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.)

• Could you please explain more clearly how did you got the formula of f(n)? Oct 13, 2016 at 12:38
• Let's reformulate the problem: put $a_0=a_{n+1}=+\infty$, then $c_i:=\min(i-l_i,r_i -i)$ is the distance from $i$ to the closest $j$ such that $a_j>a_i$. So, if $a_k=n$, for $a_1,\dots,a_{k-1}$ and for $a_{k+1},\dots,a_n$ we get the same problems and they are independent, since $a_k=n$ plays a role of $+\infty$ for all these numbers. Of course, the set of $a_i,i<k$, may be different from $\{1,\dots,k-1\}$, but it does not matter, we are interested only in the relative ordering of these numbers. Oct 13, 2016 at 12:49
• According to OEIS, this is also oeis.org/A000788. Oct 14, 2016 at 5:35