Pagini recente » Bancomat | Monitorul de evaluare | Diferente pentru problema/jpg intre reviziile 29 si 11 | Diferente pentru utilizator/rughibem intre reviziile 13 si 14 | Diferente pentru probleme-cu-secvente intre reviziile 39 si 40
Nu exista diferente intre titluri.
Diferente intre continut:
}
==
O altă metodă de calcul poate fi dedusă folosind paradigma _Divide Et Impera_. La fiecare pas împărţim şirul în jumătate şi aflăm subsecvenţele de sumă maximă din cele două jumătăţi. După aceea trebuie să găsim subsecvenţa de sumă maximă ce are un capăt în fiecare din cele două jumătăţi ale sirului. Pentru aceasta alipim sufixul de sumă maximă a primei jumătăţi cu prefixul de sumă maximă a celei de a doua.
O altă metodă de calcul poate fi dedusă folosind paradigma _Divide et Impera_. La fiecare pas împărţim şirul în jumătate şi aflăm subsecvenţele de sumă maximă din cele două jumătăţi. După aceea trebuie să găsim subsecvenţa de sumă maximă ce are un capăt în fiecare din cele două jumătăţi ale sirului. Pentru aceasta alipim sufixul de sumă maximă a primei jumătăţi cu prefixul de sumă maximă a celei de a doua.
== code(cpp) |
int getMaxSubsequence(int l, int r) {
Putem obţine un algoritm de complexitate $O(M * N)$ folosind algoritmii liniari din prima problemă, dar să vedem cum putem reduce complexitatea folosind alte abordări. Mai întâi calculăm şirul $sum[]$ al sumelor parţiale, după care împărţim şirul în $K$ subsecvenţe de lungimi egale $[N / K]$, şi păstrăm următoarele informaţii pentru fiecare din ele:
* $max[i]$ - cea mai mare valoare $sum[j]$, unde: $N/K * (i - 1) < j ≤ N/K * i$;
* $max[i]$ - cea mai mare valoare $sum[j]$, unde: $N / K * (i - 1) < j ≤ N / K * i$;
* $min[i]$ - cel mai mic $sum[j - 1]$, unde: $N/K * (i - 1) < j ≤ N/K * i$;
* $min[i]$ - cel mai mic $sum[j - 1]$, unde: $N / K * (i - 1) < j ≤ N / K * i$;
* $best[i]$ - valoarea subsecventei de suma maxima a secventei curente.
Acum, pentru a afla subsecvenţa de sumă maximă a subsecvenţei $a[x..y]$ studiem cele două cazuri posibile:
1. Dacă elementele de indice $x$ şi $y$ aparţin aceleiaşi subsecvenţe, atunci putem găsi ceea ce căutăm folosind algoritmul liniar direct pe şirul $a[x..y]$. Complexitate: $O(N/K)$.
1. Dacă elementele de indice $x$ şi $y$ aparţin aceleiaşi subsecvenţe, atunci putem găsi ceea ce căutăm folosind algoritmul liniar direct pe şirul $a[x..y]$. Complexitate: $O(N / K)$.
2. Dacă nu sunt în aceeaşi secvenţă, atunci vom împărţi şirul $a[x..y]$ în:
* zero sau mai multe subsecvenţe complete ce aparţin partiţionării,
după care rezolvăm problema pentru sufix şi prefix prin metoda liniară în $O(N/K)$, şi determinăm în $O(1)$ pentru fiecare bucată în care este spart şirul $a[x..y]$ subsecvenţa ei de sumă maximă.
după care rezolvăm problema pentru sufix şi prefix prin metoda liniară în $O(N / K)$, şi determinăm în $O(1)$ pentru fiecare bucată în care este spart şirul $a[x..y]$ subsecvenţa ei de sumă maximă.
Mai rămâne să găsim subsecvenţa de sumă maximă cu capătul în bucăţi diferite. Pentru două bucăţi fixate $i < j$, subsecvenţa de sumă maximă ce are câte un capăt în fiecare bucată are valoarea: $max[j] - min[i]$. Determinarea subsecvenţei de sumă maximă cu capetele în bucăţi diferite devine astfel de complexitate $O(K)$. Deci, pentru a rezolva o întrebare trebuie să facem $O(N/K + K)$ calcule. Pentru a reduce complexitatea problemei considerăm pe $K = sqrt(N)$. Complexitatea totală a acestei soluţii este $O(N + M * sqrt(N))$.
Mai rămâne să găsim subsecvenţa de sumă maximă cu capătul în bucăţi diferite. Pentru două bucăţi fixate $i < j$, subsecvenţa de sumă maximă ce are câte un capăt în fiecare bucată are valoarea: $max[j] - min[i]$. Determinarea subsecvenţei de sumă maximă cu capetele în bucăţi diferite devine astfel de complexitate $O(K)$. Deci, pentru a rezolva o întrebare trebuie să facem $O(N / K + K)$ calcule. Pentru a reduce complexitatea problemei considerăm pe $K = sqrt(N)$. Complexitatea totală a acestei soluţii este $O(N + M * sqrt(N))$.
Să vedem ce se întâmplă pe exemplu:
Presupunem că orice secvenţă optimă ar avea lungimea mai mare decât $K$. Atunci putem obţine o secvenţă mai mică, cu aceeaşi bază eliminând unul din capetele unei secvenţe optime. Deci este de ajuns să cautăm secvenţele optime de lungime exact $K$.
Acum putem face o parcurgere a şirului pentru a rezolva problema. Mai întâi punem într-un $min-heap$ $K$ elemente, verificăm vârful heapului şi obţinem astfel minimul secvenţei $a[1..K]$. Apoi eliminăm elementul $a[1]$ din heap şi inserăm elementul $a[K + 1]$. Prin verificarea vârfului heapului obţinem minimul secvenţei $a[2..K + 1]$. Continuăm procedeul până aflăm elementul minim pentru fiecare subsecvenţă de lungime $K$ a şirului $a$ (complexitate $O(N * log K)$). Există şi alte soluţii pentru găsirea elementului minim al unei subsecvenţe, precum folosirea unui arbore de intervale sau folosirea tehnicii $O(N * log N)/O(1)$ pentru problema _RMQ_.
Acum putem face o parcurgere a şirului pentru a rezolva problema. Mai întâi punem într-un $min-heap$ $K$ elemente, verificăm vârful heapului şi obţinem astfel minimul secvenţei $a[1..K]$. Apoi eliminăm elementul $a[1]$ din heap şi inserăm elementul $a[K + 1]$. Prin verificarea vârfului heapului obţinem minimul secvenţei $a[2..K + 1]$. Continuăm procedeul până aflăm elementul minim pentru fiecare subsecvenţă de lungime $K$ a şirului $a$ (complexitate $O(N * log K)$). Există şi alte soluţii pentru găsirea elementului minim al unei subsecvenţe, precum folosirea unui arbore de intervale sau folosirea tehnicii $O(N * log N) / O(1)$ pentru problema _RMQ_.
O observaţie importantă este aceea că dacă vrem să vedem minimul secvenţei ce se termină în $i$ şi avem $j{~1~} < j{~2~} ≤ i$ şi $a[j{~1~}] ≥ a[j{~2~}]$, atunci evident $a[j{~1~}]$ nu va fi minimul secvenţei ce se termină în $i$. Folosim o structură de date ca la soluţia cu heapuri, care adaugă elemente noi şi şterge elemente vechi, dar pe lângă elementele ce au fost inserate acum $K$ paşi şi trebuie şterse, mai ştergem şi elementele mai noi care nu ne vor mai fi utile, după cum este $a[j{~2~}]$ mai sus. Ca structură de date folosim o listă în care putem insera şi şterge de la ambele capete, un _deque_. Fiecare element inserat în deque va fi o pereche de valori, valoarea din şir şi indexul din şir $(a[i], i)$. Când o valoare este inserată în şir, ea este pusă la capătul din dreapta al şirului, dar înainte de inserare cât timp elementul din capătul şirului are valoarea mai mare decât $a[i]$ el este eliminat. La fiecare pas după o inserţie se verifică dacă elementul din capătul din stânga este mai „bătrân” de $K$ iteraţii.
h2(#problema-propuse). Probleme propuse
Pentru a vă însuşi mai bine tehnicile învăţate în acest articol, autorul vă sugerează să rezolvaţi următoarele probleme:
Pentru a vă însuşi mai bine tehnicile învăţate în acest articol, puteţi rezolva următoarele probleme:
* 'Balans':problema/balans
* 'Struţi':problema/struti
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.