Widzę wiele problemów algorytmicznych, które zawsze sprowadzają się do czegoś o długości:

Masz tablicę liczb całkowitych$h[1..n]\geq 0$, musisz znaleźć $i,j$ takie, które maksymalizuje $(h[j]-h[i])(j-i)$ w $O(n)$ czas.

Oczywiście $O(n^2)$ rozwiązaniem czasowym jest rozważenie wszystkich par, jednak czy jest jakiś sposób, aby zmaksymalizować wyrażenie $O(n)$ nie wiedząc nic więcej o właściwościach $h$?

Jednym z pomysłów, o których myślałem, jest naprawienie $j$, to musimy znaleźć $i^*$ od $1$ do $j-1$ to jest równe $\text{argmax}_i\{(h[j]-h[i])(j-i)\}$ lub $\text{argmax}_i\{h[j]j-h[j]i-h[i]j+h[i]i\}$ i odtąd $j$ jest naprawiony, wtedy potrzebujemy $\text{argmax}_i\{-h[j]i-jh[i]+ih[i]\}$.

Nie widzę jednak sposobu, aby się go pozbyć $j$warunki zależne w środku. Jakaś pomoc?

To jest $O(n\log n)$rozwiązanie. Na$O(n)$rozwiązanie wskazane przez Willarda Zhana jest dołączone na końcu tej odpowiedzi.

$O(n\log n)$ rozwiązanie

Oznacz dla wygody $f(i,j)=(h[j]-h[i])(j-i)$.

Definiować $l_1=1$, i $l_i$ być najmniejszym indeksem takim, że $l_i>l_{i-1}$ i $h[l_i]<h[l_{i-1}]$. Podobnie zdefiniuj$r_1=n$, i $r_i$ być największym indeksem takim, że $r_i<r_{i-1}$ i $h[r_i]>h[r_{i-1}]$. Sekwencje$l_1,l_2,...$ i $r_1,r_2,\ldots$ są łatwe do obliczenia $O(n)$ czas.

Przypadek, w którym nie ma $i<j$ takie, że $h[i]< h[j]$ (to znaczy $f(i,j)>0$) jest banalna. Skupiamy się teraz na sprawach niebanalnych. W takich przypadkach, aby znaleźć rozwiązanie, musimy wziąć pod uwagę tylko takie pary.

Dla każdego $i<j$ takie, że $h[i]<h[j]$, pozwolić $u$ być największym indeksem takim, że $l_u\le i$, i $v$ być najmniejszym indeksem takim, że $r_v\ge j$, następnie $h[l_u]\le h[i]$ (Inaczej $l_{u+1}\le i$ z definicji $l_{u+1}$, jest zatem sprzeczne z definicją $u$) i podobnie $h[r_v]\ge h[j]$. W związku z tym

Oznaczać $v(u)=\arg\max_{v:\ l_u<r_v}f(l_u,r_v)$mamy następujący lemat.

Para gdzie i gdzie istnieje tak że i lub takie, że i , nie może być ostatecznym optymalnym rozwiązaniem.$(l_u,r_v)$$l_u<r_v$$u_0$$u<u_0$$v<v(u_0)$$u>u_0$$v>v(u_0)$

Dowód. Zgodnie z definicjąmamy lub $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.$$

W przypadku, gdy i , zanotuj i , a także i mamy $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*}$$

Oznacza to lub

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

Tak więc jest zdecydowanie lepszym rozwiązaniem niż . Dowód dla drugiego przypadku jest podobny. $(l_u,r_{v(u_0)})$$(l_u,r_v)$$\blacksquare$

Możemy najpierw obliczyć gdzie jest długością sekwencji , a następnie rekurencyjnie obliczyć optymalne rozwiązanie spośród dla i i optymalne rozwiązanie spośród dla i . Ze względu na lemat globalne optymalne rozwiązanie musi pochodzić z .$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)$ Rozwiązanie

Niech jeśli . Dowód lematu pokazuje również ważną właściwość: dla i , jeśli , to . Oznacza to, że macierz to macierz całkowicie monotoniczna, gdzie jest długością sekwencji (więc oznacza -ty element od końca), następnie algorytm SMAWK może zastosować, aby znaleźć minimalną wartość , a więc maksymalną wartość .$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)$$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$