Veo muchos problemas algorítmicos que siempre reducen a algo las líneas de:

Tiene una matriz entera $h[1..n]\geq 0$ , necesita encontrar $i,j$ tal que maximice $(h[j]-h[i])(j-i)$ en el tiempo $O(n)$ .

Obviamente, la solución de tiempo $O(n^2)$ es considerar todos los pares, sin embargo, ¿hay alguna forma de maximizar la expresión en $O(n)$ sin saber algo más sobre las propiedades de $h$ ?

Una idea que pensé es arreglar $j$ , luego necesitamos encontrar $i^*$ de $1$ a $j-1$ que sea igual a $\text{argmax}_i\{(h[j]-h[i])(j-i)\}$ o $\text{argmax}_i\{h[j]j-h[j]i-h[i]j+h[i]i\}$ y dado que$j$ es fijo, entonces necesitamos$\text{argmax}_i\{-h[j]i-jh[i]+ih[i]\}$ .

Sin embargo, no veo forma de deshacerme de los $j$ términos dependientes en el interior. ¿Alguna ayuda?

Esta es una solución . Al final de esta respuesta se adjunta una solución O ( n ) señalada por Willard Zhan .$O(n\log n)$$O(n)$

Solución O ( n log n $O(n\log n)$

Para conveniencia, denote .$f(i,j)=(h[j]-h[i])(j-i)$

Defina , y l i será el índice más pequeño de modo que l i > l i - 1 y h [ l i ] < h [ l i - 1 ] . Del mismo modo, defina r 1 = n , y r i será el índice más grande de modo que r i < r i - 1 y h [ r i ] $l_1=1$$l_i$$l_i>l_{i-1}$$h[l_i]<h[l_{i-1}]$$r_1=n$$r_i$$r_i<r_{i-1}$ . El secuencias l 1 , l 2 , . . . y r 1 , r 2 , ... son fáciles de calcular en tiempo O ( n ) .$h[r_i]>h[r_{i-1}]$$l_1,l_2,...$$r_1,r_2,\ldots$$O(n)$

El caso donde no hay tal que h [ i ] < h [ j ] (es decir, f ( i , j ) > 0 ) es trivial. Ahora nos enfocamos en casos no triviales. En tales casos, para encontrar la solución, solo necesitamos considerar tales pares.$i<j$$h[i]< h[j]$$f(i,j)>0$

Para cada tal que h [ i ] < h [ j ] , deja que u sea el índice más grande de tal manera que l u ≤ i , y v ser el índice más pequeño tal que r v ≥ j , entonces h [ l $i<j$$h[i]<h[j]$$u$$l_u\le i$$v$$r_v\ge j$ (de lo contrario l u + 1 ≤ i por definición de l u + $h[l_u]\le h[i]$$l_{u+1}\le i$$l_{u+1}$, por lo tanto, contradice la definición de ), y de manera similar h [ r v ] ≥ h [ j ] . Por lo tanto ( h [ r v ] - h [ l u ] ) ( r v - l u ) ≥ ( h [ j ] - h [ i ] ) ( r v - l u ) ≥ ( h $u$$h[r_v]\ge h[j]$ Esto significa que solo necesitamos considerar pares ( l u , r v ) donde l u < r v .

Denote , tenemos el siguiente lema.$v(u)=\arg\max_{v:\ l_u<r_v}f(l_u,r_v)$

Un par donde l u < r v , y donde existe u 0 tal que u < u 0 y v < v ( u 0 ) o tal que u > u 0 y v > v ( u 0 ) , no puede ser una solución óptima final.$(l_u,r_v)$$l_u<r_v$$u_0$$u<u_0$$v<v(u_0)$$u>u_0$$v>v(u_0)$

$v(u_0)$

$$(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}),$$ $$(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.$$

$u<u_0$$v<v(u_0)$$h[r_v]-h[r_{v(u_0)}]<0$$r_v-r_{v(u_0)}>0$$l_u<l_{u_0}$$h[l_u]>h[l_{u_0}]$

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