9
$\begingroup$

I see many algorithmic problems that always reduce to something a long the lines of:

You have an integer array $h[1..n]\geq 0$, you need to find $i,j$ such that maximizes $(h[j]-h[i])(j-i)$ in $O(n)$ time.

Obviously the $O(n^2)$ time solution is to consider all pairs, however, is there any way we can maximize the expression in $O(n)$ without knowing something else about properties of $h$?

One idea I thought of is to fix $j$, then we need to find $i^*$ from $1$ to $j-1$ that is equal to $\text{argmax}_i\{(h[j]-h[i])(j-i)\}$ or $\text{argmax}_i\{h[j]j-h[j]i-h[i]j+h[i]i\}$ and since $j$ is fixed, then we need $\text{argmax}_i\{-h[j]i-jh[i]+ih[i]\}$.

However, I see no way of getting rid of the $j$ dependent terms inside. Any help?

$\endgroup$
  • $\begingroup$ Will an $O(n\log n)$ solution be helpful? $\endgroup$ – xskxzr Feb 7 '18 at 9:57
  • $\begingroup$ @xskxzr sure if you have any $\endgroup$ – AspiringMat Feb 7 '18 at 10:06
5
$\begingroup$

This is an $O(n\log n)$ solution. An $O(n)$ solution pointed out by Willard Zhan is appended at the last of this answer.


$O(n\log n)$ solution

For convience, denote $f(i,j)=(h[j]-h[i])(j-i)$.

Define $l_1=1$, and $l_i$ be the smallest index such that $l_i>l_{i-1}$ and $h[l_i]<h[l_{i-1}]$. Similarly, define $r_1=n$, and $r_i$ be the largest index such that $r_i<r_{i-1}$ and $h[r_i]>h[r_{i-1}]$. The sequences $l_1,l_2,...$ and $r_1,r_2,\ldots$ are easy to compute in $O(n)$ time.

The case where there are no $i<j$ such that $h[i]< h[j]$ (i.e. $f(i,j)>0$) is trivial. We now focus on non-trivial cases. In such cases, to find the solution, we only need to consider such pairs.

For each $i<j$ such that $h[i]<h[j]$, let $u$ be the largest index such that $l_u\le i$, and $v$ be the smallest index such that $r_v\ge j$, then $h[l_u]\le h[i]$ (otherwise $l_{u+1}\le i$ by definition of $l_{u+1}$, thus contradicts to the definition of $u$), and similarly $h[r_v]\ge h[j]$. Hence $$(h[r_v]-h[l_u])(r_v-l_u)\ge(h[j]-h[i])(r_v-l_u)\ge(h[j]-h[i])(j-i).$$ This means we only need to consider pairs $(l_u,r_v)$ where $l_u<r_v$.

Denote $v(u)=\arg\max_{v:\ l_u<r_v}f(l_u,r_v)$, we have the following lemma.

A pair $(l_u,r_v)$ where $l_u<r_v$, and where there exists $u_0$ such that $u<u_0$ and $v<v(u_0)$ or such that $u>u_0$ and $v>v(u_0)$, cannot be a final optimum solution.

Proof. According to the definition of $v(u_0)$, we have $$ (h[r_{v(u_0)}]-h[l_{u_0}])(r_{v(u_0)}-l_{u_0}) \ge (h[r_v]-h[l_{u_0}])(r_v-l_{u_0}), $$ or $$ (h[r_v]-h[r_{v(u_0)}])l_{u_0}+h[l_{u_0}](r_v-r_{v(u_0)})+h[r_{v(u_0)}]r_{v(u_0)}-h[r_v]r_{v(u_0)} \ge 0. $$

In the case where $u<u_0$ and $v<v(u_0)$, note $h[r_v]-h[r_{v(u_0)}]<0$ and $r_v-r_{v(u_0)}>0$, and also $l_u<l_{u_0}$ and $h[l_u]>h[l_{u_0}]$, we have $$ \begin{align*} &(h[r_v]-h[r_{v(u_0)}])l_u+h[l_u](r_v-r_{v(u_0)})\\ >\ &(h[r_v]-h[r_{v(u_0)}])l_{u_0}+h[l_{u_0}](r_v-r_{v(u_0)}). \end{align*} $$

This means $$ (h[r_v]-h[r_{v(u_0)}])l_u+h[l_u](r_v-r_{v(u_0)})+h[r_{v(u_0)}]r_{v(u_0)}-h[r_v]r_{v(u_0)} > 0, $$ or $$ (h[r_{v(u_0)}]-h[l_u])(r_{v(u_0)}-l_u) > (h[r_v]-h[l_u])(r_v-l_u). $$

So $(l_u,r_{v(u_0)})$ is a strictly better solution than $(l_u,r_v)$. Proof for the other case is similar. $\blacksquare$

We can compute $v(\ell/2)$ firstly where $\ell$ is the length of the sequence $l_1,l_2,\ldots$, then recursively compute the optimal solution $o_1$ among $(l_u,r_v)$'s for $u=1,\ldots,\ell/2-1$ and $v=v(\ell/2),v(\ell/2)+1,\ldots$, and the optimal solution $o_2$ among $(l_u,r_v)$'s for $u=\ell/2+1,\ell/2+2,\ldots$ and $v=1,\dots,v(\ell/2)$. Due to the lemma, the global optimum solution must come from $\{(l_{\ell/2},r_{v(\ell/2)}),o_1,o_2\}$.


$O(n)$ Solution

Let $f(l_u,r_v)=-\infty$ if $l_u\ge r_v$. The proof of the lemma also shows an important property: for $u>u_0$ and $v>v_0$, if $f(l_{u_0},r_{v_0})\ge f(l_{u_0},r_v)$, then $f(l_u,r_{v_0})>f(l_u,r_v)$. This means the matrix $M[x,y]:=-f(l_x,r_{c-y+1})$ is a totally monotone matrix where $c$ is the length of the sequence $r_1,r_2,\ldots$ (so $r_{c-y+1}$ means the $y$-th element from the end), then SMAWK algorithm can apply to find the minimum value of $M$, thus the maximum value of $f$.

$\endgroup$
  • 1
    $\begingroup$ What you proved is that $f(l_u,r_v)$ is a monotone matrix, so divide and conquer gives an $O(n\log n)$ algorithm. But you could actually prove that $f(l_u,r_v)$ is Monge, so that the $O(n)$ SMAWK algorithm can be applied. $\endgroup$ – Willard Zhan Feb 7 '18 at 21:12

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.