# How to maximize $(h[j]-h[i])(j-i)$ in $O(n)$

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?

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

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

• 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. – Willard Zhan Feb 7 '18 at 21:12