Diferente pentru deque-si-aplicatii intre reviziile #61 si #60

Nu exista diferente intre titluri.

Diferente intre continut:

Prima rezolvare se găseşte uşor, deoarece nu facem decât să urmărim textul: pentru fiecare poziţie $i$ fixată ({$i$} ia valorile $1$, $2$, .., $N$ succesiv) vom determina pentru aceasta secvenţa cerută, adică vom plimba un $j$ între poziţiile $i - Y$ şi $i - X$. Pentru un interval $(j, i]$ vom determina $MAX$ şi $MIN$ în $O(log{~2~}N)$ cu un arbore de intervale, iar daca diferenţa dintre acestea nu depăşeşte $Z$ vom compara cu soluţia finală. Complexitatea finală va fi $O(N * (Y - X) * log{~2~}Y)$.
p=. !deque-si-aplicatii?sir.png 60%!
 
Să presupunem că pentru poziţia curentă $i$, l-am găsit pe $j$ cuprins între $i - Y$ şi $i - X$ care îndeplineşte optimul. Ce proprietăţi are $j$?
* $i - Y ≤ j ≤ i - X$ şi $MAX - MIN ≤ Z$;

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.