Diferente pentru deque-si-aplicatii intre reviziile #112 si #113

Nu exista diferente intre titluri.

Diferente intre continut:

# Dacă $S[i{~1~}] ≤ S[i{~2~}]$ atunci, cât timp cei doi indici vor fi în intervale de tipul $[i - D, i]$, valoarea de pe poziţia $i{~2~}$ va fi întotdeauna preferată valorii de pe poziţia $i{~1~}$. Când se ajunge la un interval care nu-l mai conţine pe $i{~1~}$, $i{~2~}$ rămâne în continuare preferat.
# Dacă $S[i{~1~}] > S[i{~2~}]$ atunci şi valoarea de pe poziţia $i{~1~}$ şi cea de pe poziţia $i{~2~}$ sunt candidate la maxim, la momentul curent sau în viitor.
Cu această observaţie deducem că într-o secvenţă $[i - D, i]$ vom avea un şir strict descrescător de numere: $T{~i~} = S[i{~1~}] &gt; S[i{~2~}] &gt; ... &gt; S[i{~K~}]$, unde $S[i{~1~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~1~}]$ şi $i - D &le; j &lt; i{~1~}$, $S[i{~2~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~2~}]$ şi $i - D &le; j &lt; i{~2~}, j != i{~1~}$ dar fă poziţia $i{~1~}$ ş.a.m.d.
Cu această observaţie deducem că într-o secvenţă $[i - D, i]$ vom avea un şir strict descrescător de numere: $T{~i~} = S[i{~1~}] &gt; S[i{~2~}] &gt; ... &gt; S[i{~K~}]$, unde $S[i{~1~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~1~}]$ şi $i - D &le; j &lt; i{~1~}$, $S[i{~2~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~2~}]$ şi $i{~1~} &lt; j &lt; i{~2~}$, $S[i{~3~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~3~}]$ şi $i{~2~} &lt; j &lt; i{~3~}$ ş.a.m.d.
Şirul $T{~i~}$ are următoarele proprietăţi:
* se termină pe poziţia curentă, adică are loc egalitatea $i{~K~} = i$ întrucât poziţia $i$ nu va fi eliminată de nicio altă poziţie;

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.