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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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