Eu vejo muitos problemas algorítmicos que sempre reduzem a algo longo as linhas de:

Você tem uma matriz inteira $h[1..n]\geq 0$ , precisa encontrar $i,j$ tal que maximize $(h[j]-h[i])(j-i)$ em $O(n)$ tempo.

Obviamente, a solução do tempo de $O(n^2)$ é considerar todos os pares; no entanto, existe alguma maneira de maximizar a expressão em $O(n)$ sem saber mais alguma coisa sobre as propriedades de $h$ ?

Uma idéia em que pensei é consertar $j$ , então precisamos encontrar $i^*$ de $1$ a $j-1$ que seja igual a $\text{argmax}_i\{(h[j]-h[i])(j-i)\}$ ou $\text{argmax}_i\{h[j]j-h[j]i-h[i]j+h[i]i\}$ e como$j$ é fixo, precisamos do$\text{argmax}_i\{-h[j]i-jh[i]+ih[i]\}$ .

No entanto, não vejo como me livrar dos $j$ termos dependentes internos. Qualquer ajuda?

Esta é uma solução . Uma solução O ( n ) apontada por Willard Zhan é anexada no final desta resposta.$O(n\log n)$$O(n)$

Solução O ( n log n $O(n\log n)$

Por conveniência, denote .$f(i,j)=(h[j]-h[i])(j-i)$

Defina e l i seja o menor índice, de modo que l i > l i - 1 e h [ l i ] < h [ l i - 1 ] . Da mesma forma, defina r 1 = n e r i seja o maior índice, de modo que r i < r i - 1 e 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}$ . A sequências de L 1 , L 2 , . . . e r 1 , r 2 , … são fáceis de calcular em O ( n ) tempo.$h[r_i]>h[r_{i-1}]$$l_1,l_2,...$$r_1,r_2,\ldots$$O(n)$

O caso em que não há tal que h [ i ] < h [ j ] (isto é, f ( i , j ) > 0 ) é trivial. Agora nos concentramos em casos não triviais. Nesses casos, para encontrar a solução, precisamos apenas considerar esses pares.$i<j$$h[i]< h[j]$$f(i,j)>0$

Para cada tal que h [ i ] < h [ j ] , deixou u ser o maior índice de tal modo que l u ≤ i , e v ser o menor índice de tal modo que r v ≥ j , em seguida, h [ l u ] ≤ h [ i ] (caso contrário, l u + 1 ≤ i, por definição de l u + $i<j$$h[i]<h[j]$$u$$l_u\le i$$v$$r_v\ge j$$h[l_u]\le h[i]$$l_{u+1}\le i$$l_{u+1}$, portanto, contradiz a definição de ) e da mesma forma h [ r v ] ≥ h [ j ] . Portanto ( 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]$ Isso significa que precisamos considerar apenas pares ( l u , r v ) onde l u < r v .

Denote , temos o seguinte lema.$v(u)=\arg\max_{v:\ l_u<r_v}f(l_u,r_v)$

Um par que e onde exista tal que e ou tal que e , não possa ser uma solução ótima final.l u < r v u 0 u < u 0 v < v ( u 0 ) u > u 0 v > v ( u 0$(l_u,r_v)$$l_u<r_v$$u_0$$u<u_0$$v<v(u_0)$$u>u_0$$v>v(u_0)$

Prova. De acordo com a definição de, temos ou ( h [ r v ( u 0 ) ] - h [ l u 0 ] ) ( r v ( u 0 ) - l u 0 ) ≥ ( h [ r v ] - h [ l u 0 ] ) ( r v - l 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.$$

No caso em que e , observe e e também e , temos 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$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*}$$

Isso significa ou

$$(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,$$ $$(h[r_{v(u_0)}]-h[l_u])(r_{v(u_0)}-l_u) > (h[r_v]-h[l_u])(r_v-l_u).$$

Então é uma solução estritamente melhor que . A prova para o outro caso é semelhante. $(l_u,r_{v(u_0)})$$(l_u,r_v)$$\blacksquare$

Podemos calcular primeiro onde é o comprimento da sequência e depois calcular recursivamente a solução ideal entre s para e e a solução ideal entre s para e . Devido ao lema, a solução ideal global deve vir de .$v(\ell/2)$$\ell$$l_1,l_2,\ldots$$o_1$$(l_u,r_v)$$u=1,\ldots,\ell/2-1$$v=v(\ell/2),v(\ell/2)+1,\ldots$$o_2$$(l_u,r_v)$$u=\ell/2+1,\ell/2+2,\ldots$$v=1,\dots,v(\ell/2)$$\{(l_{\ell/2},r_{v(\ell/2)}),o_1,o_2\}$

$O(n)$ Solução

Seja se . A prova do lema também mostra uma propriedade importante: para e , se , então . Isso significa que a matriz é uma matriz totalmente monótona em que é o comprimento da sequência (então significa o ésimo elemento do final), então o algoritmo SMAWK pode ser aplicado para encontrar o valor mínimo de , portanto, o valor máximo de .$f(l_u,r_v)=-\infty$$l_u\ge r_v$$u>u_0$$v>v_0$$f(l_{u_0},r_{v_0})\ge f(l_{u_0},r_v)$M [ x , y ] : = - f ( l x , r c - y + 1 ) c r 1 , r 2 , … r c - y + 1 y M $f(l_u,r_{v_0})>f(l_u,r_v)$$M[x,y]:=-f(l_x,r_{c-y+1})$$c$$r_1,r_2,\ldots$$r_{c-y+1}$$y$$M$$f$