7
$\begingroup$

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?

$\endgroup$
2

1 Answer 1

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Could you please explain more clearly how did you got the formula of f(n)? $\endgroup$
    – newbie
    Oct 13, 2016 at 12:38
  • $\begingroup$ 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. $\endgroup$ Oct 13, 2016 at 12:49
  • 2
    $\begingroup$ According to OEIS, this is also oeis.org/A000788. $\endgroup$ Oct 14, 2016 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.