Tehnika “podeli-pa-vladaj” (engl. divide-and-conquer) ili dekompozicija podrazumeva da se problem rešava tako što se razloži na dva ili više manjih problema, koji se zatim nezavisno rekurzivno rešavaju. Obično su najveći izazovi u primeni ove tehnike osmisliti kako da se problem razloži na potrobleme i kako da se od rešenja potproblema dobije rešenje polaznog problema (oba ova koraka mogu zahtevati određeno vreme koje onda određuje ukupnu efikasnost algoritma).
Ilutrujmo ovu tehniku najpre na primeru rešavanja jedne interesantne zagonetke. Neka je data tabla dimenzije \(8 \times 8\) na kojoj nedostaje jedno polje. Zadatak je popuniti preostala 63 polja triminima (oblicima koji se dobiju kada se iz kvadrata dimenzije \(2 \times 2\) izbaci jedno polje). Na slici 9 je prikazano jedno rešenje ove zagonetke (4 moguća položaja trimino oblika su prikazana desno).
Razmislimo da li je moguće da, u cilju rešavanja, podelimo ovaj problem na potprobleme istog oblika, ali manje dimenzije. Kvadrat nije moguće podeliti na dva manja kvadrata, ali jeste moguće na četiri manja kvadrata (ako je polazni kvadrat dimenzije \(8\times 8\), tada su 4 manja kvadrata dimenzije \(4\times 4\). Postavljanjem jednog trimina u sredinu table možemo postići da u svakoj od te 4 table nedostaje po jedno polje – polje koje nedostaje tom triminu treba da bude u manjem kvadratu koji sadrži nedostajuće polje polaznog zadatka. Time se dobijaju četiri problema manje dimenzije, koji su istog oblika kao polazni - svakom manjem kvadratu nedostaje po jedno polje.
Nakon toga, svaki od 4 potproblema rešavamo rekurzivno. Svaka tabla dimenzije \(4 \times 4\) se može razložiti na 4 table dimenzije \(2 \times 2\). Postavljanjem jednog trimina možemo postići da u svakoj od te 4 table nedostaje po jedan trimino.
Na kraju, svaku tablu dimenzije \(2 \times 2\) kojoj nedostaje jedno polje možemo jednostavno popuniti postavljanjem odgovarajućeg trimina. Time se dobija rešenje prikazano na slici 9.
Važni primeri uspešne primene tehnike “podeli-pa-vladaj” su i efikasni algoritmi sortiranja koje ćemo opisati u nastavku. Naravno, sortiranje je uvek poželjno vršiti primenom bibiliotečke funkcije, koja je zasnovana na ovim ili sličnim algoritmima, pa se ovi algoritmi sortiranja danas retko ručno implementiraju. Prikazaćemo i nekoliko problema koji se rešavaju praktično istim tehnikama kojim se rešava i problem sortiranja, što ukazuje na korist poznavanja ovih opštih tehnika konstrukcije algoritama.
Algoritam merge sort deli niz na dva dela čije se dužine razlikuju najviše za 1 (ukoliko je dužina niza paran broj, onda su ova dva dela jednakih dužina), rekurzivno sortira svaki od njih i zatim objedinjuje sortirane polovine. Za objedinjavanje je neophodno koristiti dodatni, pomoćni niz. Na kraju se objedinjeni niz kopira u polazni niz. Iz rekurzije se izlazi ako je niz jednočlan (slučaj praznog niza ne može da nastupi).
Ključna operacija u ovom algoritmu je operacija objedinjavanja opisana u poglavlju 3.7.3. Funkciju ćemo prilagoditi tako da objedinjava samo delove dva vektora smeštajući rezultat u deo trećeg vektora.
// objedinjava n elemenata sortiranog niza a od pozicije p i
// m elemenata sortiranog niza b od pozicije q,
// smestajuci rezultat u sortirani vektor c od pozicije r
void merge(const vector<int>& a, int n, int p,
const vector<int>& b, int m, int q,
vector<int>& c, int r) {
vector<int> c(m + n);
int i = p, j = q, k = r;
while (i < p + n && j < q + m)
c[k++] = a[i] <= b[j] ? a[i++] : b[j++];
while (i < n)
c[k++] = a[i++];
while (j < m)
c[k++] = b[j++];
}Funkcija mergesort algoritmom merge sort sortira deo niza a[l, d], uz korišćenje niza tmp kao pomoćnog.
void mergesort(vector<int>& a, int l, int d,
vector<int>& tmp) {
if (l < d) {
int i, j;
int n = d - l + 1, s = l + n/2;
int n1 = n/2, n2 = n - n/2;
mergesort(a, l, s-1, tmp);
mergesort(a, s, d, tmp);
merge(a, n1, l, a, n2, s, tmp, 0);
// copy(tmp.begin(), tmp.begin() + (d-l+1), a.begin() + l);
for (i = l, j = 0; i <= d; i++, j++)
a[i] = tmp[j];
}
}Promenljiva n čuva broj elemenata koji se sortiraju u okviru ovog rekurzivnog poziva, a promenljiva s čuva središnji indeks u nizu između l i d. Rekurzivno se sortira n1 = n/2 elemenata između pozicija l i s-1 i n2 = n - n/2 elemenata između pozicija s i d. Nakon toga, sortirani podnizovi objedinjuju se u pomoćni niz tmp.
Pomoćni niz može se pre početka sortiranja alocirati i koristiti kroz rekurzivne pozive:
void mergesort(vector<int>& a) {
vector<int> tmp(a.size());
mergesort(a, 0, n-1, tmp);
}Napravimo jednu paralelu između rekurzivne varijante algoritama selection sort i algoritma merge sort. Osnovna ideja algoritma selection sort je da se jedan element postavi na svoje mesto i da se zatim ista metoda rekurzivno primeni na niz koji je za jedan kraći od polaznog. S obzirom na to da je pripremna akcija zahtevala \(O(n)\) operacija, ovaj rekurzivni pristup za vremensku složenost daje jednačinu \(T(n) = T(n-1) + O(n)\), te \(T(n)\) pripada klasi \(O(n^2)\). S druge strane, kod algoritma merge sort sortiranje se svodi na sortiranje dva podniza polaznog niza dvostruko manje dimenzije. S obzirom na to da korak objedinjavanja dva sortirana niza zahteva \(O(n)\) operacija, dobija se jednačina \(T(n) = 2T(n/2) + O(n)\), pa (na osnovu teoreme @thm:slozenost) \(T(n)\) pripada klasi \(O(n\log n)\). Dakle, značajno je efikasnije da se problem dimenzije \(n\) svodi na dva problema dimenzije \(n/2\) nego na jedan problem dimenzije \(n-1\). To zapažanje je u osnovi pristupa “podeli pa vladaj” (engl. divide-and-conquer) algoritama, u koje spada i algoritam merge sort. Pošto rekurzija nije repna (postoje dva rekurzivna poziva i korak objedinjavanja nakon njih), eliminacija rekurzije nije jednostavna te implementacija algoritma merge sort najčešće ostaje rekurzivna.
Razmotrimo sada i prostornu složenost ovog algoritma. Primetimo da se u funkciji drugi rekurzivni poziv vrši tek kada je prvi završen. Zato prostornu složenost opisuje jednačina \(S(n) = S(n/2) + O(1)\), te \(S(n)\) pripada klasi \(O(\log n)\) (ovde se misli na dodatnu složenost, bez pomoćnog niza). Ukupno, algoritam koristi pomoćni niz veličine \(O(n)\) i kreira najviše \(O(\log n)\) stek okvira, te njegova dodatna prostorna složenost pripada klasi \(O(\log n)\), a (ukupna) prostorna složenost pripada klasi \(O(n)\). Kako broj stek okvira na programskom steku logaritamski zavisi od broja elemenata niza, ne postoji opasnost da dođe do prekoračenja steka.
U nastavku ćemo prikazati kako se osnovna ideja algoritma merge sort može primeniti na rešavanje dva algoritamska problema.
Napiši program koji određuje koliko u nizu ima inverzija (pozicija \(0 \leq i < j < n\), takvih da je \(a_i > a_j\)).
Napomena: Broj inverzija nam daje neku meru koliko je niz blizu neopadajuće sortiranog stanja (broj inverzija neopadajuće sortiranog niza je 0, dok najviše inverzija ima niz koji je sortiran nerastuće). Broj inverzija u nizu ima primenu u analizi efikasnosti algoritama sortiranja, određivanju složenosti zadataka u veštačkoj inteligenciji, proceni sličnosti rangiranja u statistici, proveri rešivosti logičkih zagonetki poput slagalice 15 i slično.
Sa standardnog ulaza se unosi broj \(n\) (\(1 \leq n \leq 10^5\)) i zatim \(n\) celih brojeva, svaki u posebnom redu.
Na standardni izlaz ispisati samo traženi broj inverzija.
5 3 1 4 2 5
3
Grubom silom se zadatak rešava tako što se pomoću ugnežđenih petlji ispitaju svi parovi pozicija \(0 \leq i < j < n\) i prebroje svi slučajevi kada je \(a_i > a_j\) (brojimo elemente filtrirane serije). Složenost ovog algoritma odgovara broju parova, a to je \(O(n^2)\).
long long broj_inverzija(const vector<int>& a) {
int n = a.size();
long long broj = 0;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
if (a[j] < a[i])
broj++;
return broj;
}#include <iostream>
#include <vector>
using namespace std;
long long broj_inverzija(const vector<int>& a) {
int n = a.size();
long long broj = 0;
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
if (a[j] < a[i])
broj++;
return broj;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << broj_inverzija(a) << endl;;
return 0;
}Razmotrimo kako bismo problem rešili dekompozicijom. Prazan niz i jednočlan niz nemaju inverzija. Ako je niz podeljen na dve polovine, ukupan broj inverzija jednak je zbiru broja inverzija među elementima prve polovine, broja inverzija među elementima druge polovine i broja parova elemenata gde prvi element pripada prvoj, drugi element pripada drugoj polovini i prvi je veći od drugog. Prva dva broja možemo odrediti rekurzivno i ostaje samo pitanje kako efikasno odrediti treći broj. Da bismo dobili ukupnu složenost \(O(n\log{n})\) taj problem je potrebno rešiti u složenosti \(O(n)\) tako da ispitivanje svih parova elemenata iz prve i druge polovine ne dolazi u obzir. Zadatak bi se mogao lakše rešiti ako bi prva i druga polovina bile sortirane (ključni uvid je da sortiranje elemenata tih polovina ne menja treći broj). Tada možemo primeniti tehniku dva pokazivača i veoma slično kao u slučaju objedinjavanja dva sortirana niza odrediti željeni treći broj. Međutim, umesto da sortiramo polovine zasebno, algoritam sortiranja možemo integrisati sa brojanjem inverzija i proširiti invarijantu naše funkcije (ojačati induktivnu hipotezu) tako da funkcija vraća broj inverzija i ujedno i sortira niz. Na osnovu invarijante, rekurzivni pozivi će sortirati levu i desnu polovinu, a da bismo je održali, tokom određivanja trećeg broja vršićemo objedinjavanje sortiranih nizova (isto kao u algoritmu MergeSort).
Primer 5.1.1. Pokažimo na jednom primeru kako možemo da prebrojimo inverzije tokom objedinjavanja. Neka je dat niz \(1, 3, 5, 4, 7, 6, 2, 8\). Sve inverzije u njemu su \((3, 2)\), \((5, 4)\), \((5, 2)\), \((4, 2)\), \((7, 6)\), \((7, 2)\) i \((6, 2)\) i ima ih 7.
Podelom se dobijaju polovine \(1, 3, 5, 4\) i \(6, 7, 2, 8\). Rekurzivni pozivi sortiraju polovine niza i u prvoj polovini pronalaze inverziju \((5, 4)\), a u drugoj polovini inverzije \((7, 6)\), \((7, 2)\) i \((6, 2)\). Nedostaju još inverzije gde je prvi element iz prve, a drugi iz druge polovine niza (to su inverzije \((3, 2)\), \((4, 2)\) i \((5, 2)\)). Sortirane polovine su \(1, 3, 4, 5\) i \(2, 6, 7, 8\). Započnimo objedinjavanje ovih nizova.
Na početku se porede elementi \(1\) i \(2\). Pošto je element iz leve polovine manji, on se prebacuje u rezultujući niz. Pošto je druga polovina sortirana, znamo da je element \(1\) manji od svih elemenata druge polovine, pa on učestvuje u 0 inverzija.
Nakon toga se porede elementi \(3\) i \(2\). Ovaj put je element desne polovine \(2\) manji od elementa iz leve polovine \(3\), pa zato njega prebacujemo u rezultat. Element \(2\) je manji od elementa \(3\), a pošto je leva polovina sortirana, manji je i od svih elemenata iza njega. Zato znamo da on učestvuje u 3 inverzije.
Nakon toga se porede elementi \(3\) i \(6\). Element \(3\) je manji od elementa \(6\), pa se on prebacuje u rezultat. Pošto se element \(6\) nalazi na poziciji \(1\) u desnoj polovini i pošto je desna polovina sortirana, možemo zaključiti da element \(3\) učestvuje u jednoj inverziji (to je ona sa elementom \(2\)).
Nakon toga se porede elementi \(4\) i \(6\). Element \(4\) je manji od elementa \(6\), pa se on prebacuje u rezultat. Pošto se element \(6\) nalazi na poziciji \(1\) u desnoj polovini i pošto je desna polovina sortirana, možemo zaključiti da element \(4\) učestvuje u jednoj inverziji (to je ona sa elementom \(2\)).
Nakon toga se porede elementi \(5\) i \(6\). Element \(5\) je manji od elementa \(6\), pa se on prebacuje u rezultat. Pošto se element \(6\) nalazi na poziciji \(1\) u desnoj polovini i pošto je desna polovina sortirana, možemo zaključiti da element \(5\) učestvuje u jednoj inverziji (to je ona sa elementom \(2\)).
Pošto su svi elementi iz prve polovine prepisani u rezultujući niz, prepisuju se elementi iz druge polovine. Prepisuje se element \(6\) i pošto je on veći od svih elemenata iz prve polovine, on ne učestvuje ni u jednoj inverziji. Isto važi i za elemente \(7\) i \(8\).
Dakle, prilikom objedinjavanja za svaki element možemo izračunati broj inverzija u kojima učestvuje (naravno, govorimo samo o inverzijama između dve polovine niza).
Kada se u rezultujući niz prepisuje element iz leve polovine niza on je strogo veći od svih elemenata desne polovine koji su već prepisani (njihov broj se lako određuje na osnovu vrednosti desnog pokazivača), a manji ili jednak od ostalih elemenata desne polovine, pa je broj inverzija u kojima on učestvuje jednak vrednosti desnog pokazivača (od koje treba oduzeti poziciju početka desne polovine niza, ako njeni elementi nisu smešteni od pozicije 0). Ako desna polovina počinje na poziciji \(s+1\), tada se broj inverzija može odrediti kao \(p_d - s - 1\).
Kada se u rezultujući niz prepisuje element iz desne polovine niza, on je strogo manji od tekućeg elementa u levoj polovini i svih elemenata iza njega. Dakle, broj inverzija u kojima učestvuje može se izračunati tako što se od ukupnog broja elemenata leve polovine oduzme pozicija levog pokazivača (naravno, opet je potrebno u obzir uzeti i poziciju na kojoj počinje leva polovina niza). Ako se leva polovina završava na poziciji \(s\) onda se broj inverzija može izračunati kao \(s + 1 - p_l\).
Ukupan broj inverzija se može izračunati bilo tako što se sabere broj pojedinačnih inverzija za svaki element iz leve polovine (tada brojač uvećavamo u trenutku kada se prebacuje element iz leve polovine) ili tako što se sabere broj pojedinačnih inverzija za svaki element iz desne polovine (tada brojač uvećavamo u trenutku kada se prebacuje element iz desne polovine). Možda je malo jednostavnije sabrati inverzije svih elemenata u desnoj polovini, jer tada u fazi prepisivanja elemenata preostale polovine (kada se jedna polovina iscrpi) nema potrebe za ažuriranjem broja inverzija. Zaista, ako su preostali samo elementi leve polovine, za svaki element desne polovine je već izračunat i sabran broj inverzija, a ako su preostali samo elementi desne polovine, pošto su iscrpljeni svi elementi leve polovine, ti preostali elementi desne polovine ne učestvuju ni u jednoj inverziji. Ipak, pošto rekurzivna funkcija pored izračunavanja broja inverzija treba da sortira niz, preostale elemente moramo prepisati u rezultat (čak iako broj inverzija znamo i ranije).
long long broj_inverzija(vector<int>& a, int l, int d,
vector<int>& b) {
if (l >= d)
return 0;
int s = l + (d - l) / 2;
long long broj = 0;
broj += broj_inverzija(a, l, s, b);
broj += broj_inverzija(a, s+1, d, b);
int pl = l, pd = s+1, pb = 0;
while (pl <= s && pd <= d) {
if (a[pl] <= a[pd])
b[pb++] = a[pl++];
else {
broj += s - pl + 1;
b[pb++] = a[pd++];
}
}
while (pl <= s)
b[pb++] = a[pl++];
while (pd <= d)
b[pb++] = a[pd++];
copy(begin(b), next(begin(b), d-l+1), next(begin(a), l));
return broj;
}
long long broj_inverzija(const vector<int>& a) {
vector<int> tmp1(a.size()), tmp2(a.size());
// kopiramo vektor a u vektor tmp1 da mogao da se menja
copy(begin(a), end(a), begin(tmp1));
return broj_inverzija(tmp1, 0, a.size()-1, tmp2);
}#include <iostream>
#include <vector>
using namespace std;
long long broj_inverzija(vector<int>& a, int l, int d,
vector<int>& b) {
if (l >= d)
return 0;
int s = l + (d - l) / 2;
long long broj = 0;
broj += broj_inverzija(a, l, s, b);
broj += broj_inverzija(a, s+1, d, b);
int pl = l, pd = s+1, pb = 0;
while (pl <= s && pd <= d) {
if (a[pl] <= a[pd])
b[pb++] = a[pl++];
else {
broj += s - pl + 1;
b[pb++] = a[pd++];
}
}
while (pl <= s)
b[pb++] = a[pl++];
while (pd <= d)
b[pb++] = a[pd++];
copy(begin(b), next(begin(b), d-l+1), next(begin(a), l));
return broj;
}
long long broj_inverzija(const vector<int>& a) {
vector<int> tmp1(a.size()), tmp2(a.size());
// kopiramo vektor a u vektor tmp1 da mogao da se menja
copy(begin(a), end(a), begin(tmp1));
return broj_inverzija(tmp1, 0, a.size()-1, tmp2);
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << broj_inverzija(a) << endl;;
return 0;
}Kao algoritam merge sort, i algoritam quick sort pripada grupi podeli-pa-vladaj algoritama. Slično kao kod algoritma selection sort, u svakom koraku težimo da neki element niza dovedemo na svoju poziciju u sortiranom nizu. Umesto da to obavezno bude minimum (ili maksimum), u algoritmu quick sort u svakom koraku na svoje mesto dovodi se neki element (obično nazivan pivor) koji je poželjno blizu sredine niza. Međutim, da bi nakon toga problem mogao biti sveden na sortiranje dva manja podniza, potrebno je prilikom dovođenja pivota na svoje mesto grupisati sve elemente manje od njega ili jednake njemu levo od njega, a sve elemente veće od njega desno od njega (ako se niz sortira neopadajuće). To pregrupisavanje elemenata niza, korak particionisanja (već opisano u poglavlju @subsec:dva_pokazivaca), ključni je korak algoritma quick sort.
Primetimo da je u algoritmu merge sort razdvajanje na potprobleme trivijalno, a objedinjavanje rezultata netrivijalno, a u algoritmu quick sort je suprotno: razdvajanje na potprobleme je netrivijalno, a objedinjavanje rezultata je trivijalno.
Algoritam quick sort može se implementirati na sledeći način.
void quicksort(vector<int>& a, int l, int d)
{
if (l < d) {
// pocetni polozaj pivota
int p = izbor_pivota(a, l, d);
// pivot dovodimo na pocetak niza
swap(a[l], a[p]);
// particionisemo niz i odredjujemo novi polozaj pivota
p = particionisi(a, l, d);
// rekurzivno sortiramo delove levo i desno od pivota
quicksort(a, l, p - 1);
quicksort(a, p + 1, d);
}
}Poziv quicksort_(a, l, d) sortira deo niza a[l, d]. Funkcija quicksort se onda jednostavno implementira:
void quicksort(vector<int>& a)
{
quicksort(a, 0, a.size()-1);
}Funkcija izbor_pivota bira za pivot neki element niza a[l, d] i vraća njegov indeks (u nizu a). Pozivom funkcije razmeni pivot se postavlja na poziciju l. Funkcija particionisanje vrši particionisanje niza (pretpostavljajući da se pre particionisanja pivot nalazi na poziciji l) i vraća poziciju na kojoj se nalazi pivot nakon particionisanja. Funkcija se poziva samo za nizove koji imaju više od jednog elementa, te joj je preduslov da je l manje od d. Postuslov funkcije particionisi je da je (multi)skup elemenata niza a nepromenjen nakon njenog poziva, međutim njihov redosled je takav da su svi elementi niza a[l, p-1] manji od ili jednaki elementu a[p], dok su svi elementi niza a[p+1, d] veći od ili jednaki elementu a[p].
Na osnovu teoreme @thm:slozenost, kako bi se dobila jednačina \(T(n) = 2T(n/2)+O(n)\) i vremenska složenost \(O(n \log n)\), funkcija particionisi (tj. korak particionisanja) treba da bude izvršena u linearnom vremenu \(O(n)\). U nastavku će biti prikazano nekoliko algoritama particionisanja koji ovo zadovoljavaju. Dalje, potrebno je da pozicija pivota nakon particionisanja bude blizu sredini niza (kako bi dužine dva podniza na koje se problem svodi bile približno jednake \(n/2\)). Međutim, određivanje središnjeg člana u nizu brojeva (što predstavlja idealnu strategiju za funkciju izbor_pivota) je problem koji nije značajno jednostavniji od samog sortiranja. S obzirom na to da se očekuje da je implementacija funkcije izbor_pivota brza (obično \(O(1)\)), obično se ne garantuje da će za pivot biti izabiran upravo srednji član, već se koriste heuristike koje za pivot biraju elemente koji nisu daleko od središnje pozicije u nizu.
Naglasimo da se za svaku strategiju izbora pivota (koja ne koristi slučajno izabrane brojeve) može konstruisati niz takav da u svakom koraku izbor pivota bude najgori mogući — onaj koji deli niz na nizove dužine \(0\) i \(n-1\), što dovodi do jednačine \(T(n) = T(n-1) + O(n)\) i kvadratne vremenske složenosti i linearne dodatne prostorne složenosti (u odnosu na dužinu niza). Međutim, većina strategija je takva da se u prosečnom slučaju može očekivati da se dužine podnizova ne razlikuju mnogo, te daju prosečnu vremensku složenost \(O(n\log n)\) i prosečnu dodatnu prostornu složenost \(O(\log n)\) (jer algoritam radi u mestu i na programskom steku se u proseku formira \(O(\log n)\) stek okvira).
U praksi, najbolje rezultate kod sortiranja dugačkih nizova daje upravo algoritam quick sort. Međutim, za sortiranje kraćih nizova naivni algoritmi (na primer, insertion sort) mogu da se pokažu pogodnijim. Većina realnih implementacija algoritma quick sort koristi hibridni pristup — izlaz iz rekurzije se vrši kod nizova koji imaju nekoliko desetina elemenata i na njih se primenjuje insertion sort.
Korak particionisanja može se implementirati kao što je to opisano u poglavlju 3.7.1. Na primer,
int particionisi(vector<int>& a, int l, int d)
{
int m = l;
for (int t = l+1; t <= d; t++)
if (a[t] >= a[l])
swap(a[++m], a[t]);
swap(a[m], a[l]);
return m;
}Još jedan način particionisanja zasnovan je na Dajkstrinom algoritmu “trobojke” prikazanom u zadatku [Trobojka]. U ovom slučaju, radi se malo više od onoga što postuslov striktno zahteva — niz se permutuje tako da prvo idu svi elementi striktno manji od pivota, zatim sva pojavljivanja pivota i na kraju svi elementi striktno veći od pivota. Ovaj pristup particionisanju je pogodan za nizove u kojima ima puno ponovljenih elemenata, jer se u jednom koraku veliki broj elemenata dovodi na svoje mesto i rekurzivni pozivi obrađuju kraće podnizove.
Kao što je već rečeno, iako je poželjno da se pivot izabere tako da podeli niz na dve potpuno jednake polovine, to bi trajalo previše tako da se obično pribegava heurističkim rešenjima. Ukoliko se može pretpostaviti da su elementi niza slučajno raspoređeni (što se uvek može postići ukoliko se pre primene sortiranja niz permutuje na slučajan način), bilo koji element niza se može uzeti za pivot. Na primer,
int izbor_pivota(int a[], int l, int d)
{
return l;
}ili
int izbor_pivota(int a[], int l, int d)
{
return nasumican_broj(l, d);
}Nešto bolje performanse mogu se postići ukoliko se, na primer, za pivot uzima srednji od tri slučajno izabrana elementa niza.
U nastavku ćemo prikazati algoritam quick select, koji ilustruje kako se osnovna ideja algoritma brzog sortiranja može primeniti na rešavanje nekoliko srodnih problema primenom delimičnog sortiranja niza (engl. partial sort). Delimičnim sortiranjem u vremenu \(O(n)\) možemo na prvih \(k\) pozicija u nizu dovesti \(k\) najmanjih (ili najvećih) elemenata niza (u proizvoljnom redosledu), odrediti neku statistiku tih \(k\) elemenata (zbir, proizvod, minimum, maksimum i slično), odrediti \(k\)-ti po redu element u nizu (tzv. rangovske statistike), odrediti medijanu niza i slično.
Ovaj zadatak je ponovljen u cilju ilustrovanja različitih tehnika rešavanja.
Zadatak se može rešiti i tako što će se niz sortirati bibliotečkom funkcijom za sortiranje. Ako se niz sortira nerastuće, onda je nakon sortiranja potrebno sabrati prvih \(k\) elemenata niza, a ako se sortira neopadajuće, onda je nakon sortiranja potrebno sabrati poslednjih \(k\) elemenata niza (sortiranje neopadajuće je obično podrazumevani način sortiranja i lakše ga je realizovati).
Ako se sortiranje vrši bibliotečkim funkcijama, vremenska složenost ovog rešenja je \(O(n\cdot\log(n))\), dok je memorijska složenost jednaka \(O(n)\).
Može se primetiti da ovakav algoritam nepotrebno gubi vreme precizno određujući redosled tj. sortirajući elemente koji su manji od prvih \(k\) i određujući precizan redosled prvih \(k\) elemenata. Naime, da bi se sabralo prvih \(k\) elemenata oni ne moraju biti poređani, već je samo potrebno na početak niza (ili na kraj) dovesti prvih \(k\) elemenata, a iza njih (ili ispred) postaviti ostale elemente tj. razdvojiti te dve grupe elemenata, pri čemu je redosled elemenata unutar svake od grupa irelevantan.
// ucitavamo ulazne podatke
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// sortiramo niz nerastuce
sort(begin(a), end(a), greater<int>());
// sabiramo prvih k elemenata niza
int s = accumulate(begin(a), next(begin(a), k), 0);
// ispisujemo rezultat
cout << s << endl;#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional> // zbog greater<int>() u pozivu funkcije sort
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo ulazne podatke
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// sortiramo niz nerastuce
sort(begin(a), end(a), greater<int>());
// sabiramo prvih k elemenata niza
int s = accumulate(begin(a), next(begin(a), k), 0);
// ispisujemo rezultat
cout << s << endl;
}Algoritam brze selekcije (QuickSelect) predstavlja modifikaciju algoritma brzog sortiranja. Brza selekcija se koristi da se niz podeli tako da se na prvih \(k\) mesta nađe \(k\) najvećih (ili najmanjih) elemenata niza, da se na mestima iza njih nalaze elementi manji (ili veći) od njih, pri čemu je redosled elemenata u svakoj od te dve grupe proizvoljan. Pošto je redosled elemenata u grupama proizvoljan, može se dobiti efikasniji algoritam od onoga u kom bi se sortirao ceo niz (jer redosled elemenata u svakoj grupi može biti proizvoljan).
Algoritam brze selekcije se zasniva na koraku particionisanja, identičnom kao u algoritmu brzog sortiranja, koji u linearnoj složenosti elemente niza uređuje tako da se prvo u nizu nađu elementi koji su manji od nekog datog elementa (pivota), da se nakon njih nalazi pivot i da nakon toga slede elementi koji su veći od pivota. Redosled elemenata u svakoj od ovih grupa je potpuno proizvoljan. Ako se pivot javlja više puta, ostala pojavljivanja pivota mogu biti bilo levo, bilo desno od pivota (često se uzima da se levo od pivota nalaze elementi manji ili jednaki od njega, a desno elementi strogo veći od njega ili obratno). Kao kod algoritma brzog sortiranja, za particionisanje se mogu koristiti postupci zasnovani na tehnici dva pokazivača.
Pošto se u zadatku traži zbir \(k\) najvećih elemenata u nizu, jednostavnosti radi, pretpostavićemo da elemente niza sortiramo u obratnom redosledu – želimo da se \(k\) najvećih elemenata niza nađe na njegovom početku.
Osovni algoritam je rekurzivan i parametar rekurzije su granice \(l\) i \(d\) i broj \(k\), i zadatak algoritma je da deo niza na pozicijama \([l, d]\) reorganizuje tako da na početku bude \(k\) najvećih elemenata tog dela niza.
Izlaz iz rekurzije može biti kada je \(k\) veće ili jednako od dužine segmenta \([l, d]\), tj. kada je \(k \geq d - l + 1\) i tada svi elementi niza spadaju među prvih \(k\). Ako je u startu \(k \leq n\), gde je \(n\) broj elemenata niza, tada \(k\) nikada neće biti strogo veće od dužine segmenta \([l, d]\) (ali može biti jednako).
Nakon izbora pivota i particionisanja, poznata je pozicija na kojoj se pivot nalazi. Neka je to neka pozicija \(m\) (važi da je \(l \leq m \leq d\)).
Ako je broj elemenata levo od pivota (vrednost \(m - l\)) veća ili jednaka \(k\) onda je dovoljno naći \(k\) najvećih elemenata levog dela niza. Naime svi elementi u levom delu niza su veći ili jedanki od pivota i od elemenata u desnom delu, pa se svih \(k\) najvećih elemenata dela niza sa pozicija \([l, d]\) nalaze u levom delu niza, ispred pivota. Dakle, potrebno je izvršiti rekurzivni poziv za interval \([l, m-1]\) i broj \(k\) tj. pronaći \(k\) najvećih elemenata u delu niza na pozicijama \([l, m-1]\).
U suprotnom se zaključno sa pivotom nalazi \(m - l + 1\) od \(k\) najvećih elemenata niza i zato je potrebno u desnom delu odrediti još \(k - (m - l + 1)\) najvećih elemenata iz tog dela, tako da se rekurzivni poziv vrši za interval \([m+1, d]\) i broj \(k - m + l - 1\).
Primetimo da u funkciji postoji samo jedan rekurzivni poziv i to repni, tako da se on može jednostavno eliminisati.
// QuickSelect - odredjujemo najvecih k elemenata niza a tj.
// niz permutujemo tako da se najvecih k elemenata nadju na
// prvih k pozicija (u proizvoljnom redosledu)
void qsortK(vector<int>& a, int l, int d, int k) {
if (k >= d - l + 1)
return;
// niz particionisemo tako da se pivot (element a[l]) dovede
// na svoje mesto, da ispred njega budu svi elementi koji su
// veci ili jednaki od njega, a da iza njega budu svi
// elementi veci od njega
int m = particionisanje(a, l, d);
if (k <= m - l)
// svih k elemenata su levo od pivota -
// obradjujemo deo ispred pivota
qsortK(a, l, m - 1, k);
else
// mozda su neki kod k najvecih iza pivota -
// obradjujemo deo iza pivota
qsortK(a, m+1, d, k - (m - l + 1));
}
// QuickSelect - pomocna funkcija zbog lepseg interfejsa
void qsortK(vector<int>& a, int k) {
qsortK(a, 0, a.size() - 1, k);
}#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int particionisanje(vector<int>& a, int l, int d)
{
int m = l;
for (int t = l+1; t <= d; t++)
if (a[t] >= a[l])
swap(a[++m], a[t]);
swap(a[m], a[l]);
return m;
}
// QuickSelect - odredjujemo najvecih k elemenata niza a tj.
// niz permutujemo tako da se najvecih k elemenata nadju na
// prvih k pozicija (u proizvoljnom redosledu)
void qsortK(vector<int>& a, int l, int d, int k) {
if (k >= d - l + 1)
return;
// niz particionisemo tako da se pivot (element a[l]) dovede
// na svoje mesto, da ispred njega budu svi elementi koji su
// veci ili jednaki od njega, a da iza njega budu svi
// elementi veci od njega
int m = particionisanje(a, l, d);
if (k <= m - l)
// svih k elemenata su levo od pivota -
// obradjujemo deo ispred pivota
qsortK(a, l, m - 1, k);
else
// mozda su neki kod k najvecih iza pivota -
// obradjujemo deo iza pivota
qsortK(a, m+1, d, k - (m - l + 1));
}
// QuickSelect - pomocna funkcija zbog lepseg interfejsa
void qsortK(vector<int>& a, int k) {
qsortK(a, 0, a.size() - 1, k);
}
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo ulazne podatke
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// odredjujemo prvih k najvecih elemenata niza
qsortK(a, k);
// sabiramo prvih k elemenata niza i ispisujemo rezultat
int s = 0;
for (int i = 0; i < k; i++)
s += a[i];
cout << s << endl;
return 0;
}Primer 5.2.1.
Prikažimo rad ovog algoritma na primeru pronalaženja 5 najvećih elemenata niza \(5, 9, 6, 3, 10, 13, 1, 7, 8, 14, 2\). Važi da je \(k=5\) i \(n=11\).
Na početku je \([l, d]=[0, n-1]=[0, 10]\). Posle particionisanja dobija se niz \(9, 6, 10, 13, 7, 8, 14, {\it 5}, 3, 1, 2\), gde je pivot \(5\) završio na poziciji \(m=7\). Pošto je broj elemenata levo od pivota \(m - l = 7\) veći od \(k=5\), rekurzivno pronalazimo 5 najvećih elemenata u delu niza na pozicijama u intervalu \([l, m-1] = [0, 6]\).
Particionišemo deo niza određen sa \([l, d] = [0, 6]\). Posle particionisanja dobija se niz \(10, 13, 14, {\it 9}, 6, 7, 8, {\bf 5}, {\bf 3}, {\bf 1}, {\bf 2}\), gde je pivot \(9\) završio na poziciji \(m=3\). Ovaj put je broj elemenata levo od pivota \(m - l = 3\) strogo manji od \(k=5\). Zato je potrebno rekurzivno ponaći \(k - (m - l + 1) = 1\) najveći element u delu niza na pozicijama \([m+1, d] = [4, 6]\)
Particionišemo deo niza određen sa \([l, d] = [4, 6]\). Posle particionisanja dobija se niz \({\bf 10}, {\bf 13}, {\bf 14}, {\bf 9}, 7, 8, {\it 6}, {\bf 5}, {\bf 3}, {\bf 1}, {\bf 2}\), gde je pivot \(6\) završio na poziciji \(m=6\). Broj elemenata levo od pivota \(m-l = 2\) i on je veći od \(k\), pa rekurzivno tražimo \(k=1\) najveći element u delu niza na pozicijama \([l, m-1] = [4, 5]\).
Particionišemo deo niza određen sa \([l, d] = [4, 5]\). Posle particionisanja dobija se niz \({\bf 10}, {\bf 13}, {\bf 14}, {\bf 9}, 8, {\it 7}, {\bf 6}, {\bf 5}, {\bf 3}, {\bf 1}, {\bf 2}\), gde je pivot \(7\) završio na poziciji \(m=5\). Broj elemenata levo od pivota \(m-l = 1\) i on je jednak \(k\), pa rekurzivno tražimo \(k=1\) najveći element u delu niza na pozicijama \([l, m-1] = [4, 4]\).
Pošto je dužina \(d-l+1\) intervala \([l, d] = [4, 4]\) jednaka \(k = 1\), postupak je završen. Konačno stanje niza je \(10, 13, 14, 9, 8, 7, 6, 5, 3, 1, 2\). Primetimo da niz nije sortiran opadajuće, ali smo sigurni da se 5 najvećih elemenata niza sada nalazi na njegovom početku.
Primetimo i da dokazivanje zaustavljanja algoritma nije sasvim trivijalno. Ako je \(k\) u startu veće od dužine niza, algoritam će se odmah zaustaviti. U suprotnom će sve vreme izvršavanja algoritma važiti invarijanta da je \(0 \leq k \leq d - l + 1\) (u trenutku kada se postigne gornja jednakost, algoritam će se zaustaviti), dok će se vrednost \(d - l + 1\) smanjivati kroz rekurzivne pozive.
Ako je \(k \leq m - l\), izvršiće se rekurzivni poziv za \(l' = l\), \(d' = m-1\) i \(k' = k\). Pošto je \(m \leq d\), važi i da je \(m < d + 1\). Zato je \(d' - l' + 1 = m - 1 - l + 1 = m - l < d - l + 1\).
Važi i da je \(k' \leq d' - l' + 1\), jer je \(k' = k \leq m - l = d' - l' + 1\). Važi i da je \(0 \leq k' = k\).
Ako je \(k > m - l\), izvršiće se rekurzivni poziv za \(l' = m+1\), \(d' = d\) i \(k' = k - (m - l + 1)\). Tada je \(d' - l' + 1 = d - (m+1) + 1 = d - m\). Pošto je \(l \leq m\), važi da je \(d' - l' + 1 = d - m \leq d - l < d - l + 1\).
Važi i da je \(k' \leq d' - l' + 1\). Zamenom dobijamo da je taj uslov ekvivalentan \(k - (m - l + 1) \leq d - (m + 1) + 1\), tj. \(k + l - 1 \leq d\), no to važi, jer je \(k \leq d - l + 1\).
Pošto je \(k > m - l\), važi i da je \(k \geq m - l + 1\), pa je \(k' = k - (m - l + 1) \geq 0\).
Iz ove analize jasno je i da ako je \(k\leq n\), tada uslov zaustavljanja algoritma (izlaz iz rekurzije) može biti i kada niz postane prazan tj. kada je \(l - d + 1\) postane \(0\). Takođe, uslov zaustavljanja bi mogao biti i to da je \(k = 0\).
Pod pretpostavkom da će pivot deliti niz na delove koji su otprilike jednake veličine, složenost ovog algoritma se opisuje jednačinom \(T(n) = T(n/2) + O(n), T(0) = O(1)\), čije je rešenje \(T(n) = O(n)\). Može se dokazati da je prosečna složenost algoritma brze selekcije linearna, dok je složenost najgoreg slučaja kvadratna (što se veoma retko dešava, kao i u algoritmu Quick sort). Pošto se ceo niz učitava i čuva u memoriji i prostorna složenost je \(O(n)\).
U jeziku C++ bibliotečka funkcija nth_element vrši podelu niza tako da se na poziciji \(n\) nađe element koji tu i pripada u sortiranom redosledu, da se ispred te pozicije nađu elementi koji su svi manji ili jednaki od njega, a da se iza te pozicije nađu elementi koji su svi veći ili jednaki od njega. Funkciji se prosleđuje iterator na početak dela niza (vektora) koji se obrađuje (obično dobijen pomoću begin), iterator na neku poziciju na sredini niza i iterator koji ukazuje neposredno iza kraja niza (obično dobijen pomoću end). Ako središnji iterator ukazuje na \(n\)-tu poziciju u nizu nakon primene funkcije na toj poziciji će se naći \(n\)-ti po veličini element, dok će svi elementi levo od njega biti manji ili jednaki od svih elemenata desno od njega. Recimo i da postoji funkcija partial_sort koja je slična prethodnoj ali ujedno elemente ispred date pozicije uređuje (soritra) po veličini, međutim, u ovom slučaju to nam nije potrebno i time bi se samo nepotrebno gubilo vreme.
// niz particionisemo tako da je k-ti element na svom mestu i
// da su svi elementi ispred njega manji ili jednaki od svih
// elemenata iza
nth_element(a.begin(), next(a.begin(), k), a.end(),
greater<int>());
// odredjujemo i ispisujemo zbir prvih k elemenata
cout << accumulate(a.begin(), next(a.begin(), k), 0) << endl;#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo ulazne podatke
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// niz particionisemo tako da je k-ti element na svom mestu i
// da su svi elementi ispred njega manji ili jednaki od svih
// elemenata iza
nth_element(a.begin(), next(a.begin(), k), a.end(),
greater<int>());
// odredjujemo i ispisujemo zbir prvih k elemenata
cout << accumulate(a.begin(), next(a.begin(), k), 0) << endl;
return 0;
}Prikažimo sada i još jedno rešenje problema određivanja maksimalnog zbira segmenta niza, koje je zasnovano na tehnici “podeli-pa-vladaj”.
Ovaj zadatak je ponovljen u cilju ilustrovanja različitih tehnika rešavanja.
Dekompozicija nam sugeriše da je poželjno da niz podelimo na dva podniza jednake dužine čija rešenja možemo da konstruišemo na osnovu induktivne hipoteze (najčešće rekurzivnim pozivima). Bazu i ovaj put čini slučaj praznog niza, koji sadrži samo prazan segment čiji je zbir nula. Fiksirajmo središnji element niza. Sve segmente niza možemo da grupišemo u tri grupe: segmente koji su u potpunosti levo od središnjeg elementa, segmente koji su u potpunosti desno od središnjeg elementa i segmente koji sadrže središnji element. Najveće zbirove segmenata u prvoj i u drugoj grupi znamo na osnovu induktivne hipoteze. Najveći zbir segmenta u trećoj grupi možemo lako odrediti analizom svih segmenata koji sadrže središnji element: krećemo od jednočlanog segmenta koji sadrži samo središnji element i inkrementalno se širimo nalevo dodajući jedan po jedan element i računajući tekući maksimum, a zatim krećemo od maksimalnog segmenta proširenog nalevo i inkrementalno ga proširujemo jednim po jednim elementom nadesno, tražeći novi maksimum.
int maksZbirSegmenta(const vector<int>& a, int l, int d) {
if (l > d)
return 0;
int s = l + (d - l) / 2;
int maks_zbir_levo = maksZbirSegmenta(a, l, s-1);
int maks_zbir_desno = maksZbirSegmenta(a, s+1, d);
int zbir_sredina = a[s];
int maks_zbir_sredina = zbir_sredina;
for (int i = s-1; i >= l; i--) {
zbir_sredina += a[i];
if (zbir_sredina > maks_zbir_sredina)
maks_zbir_sredina = zbir_sredina;
}
zbir_sredina = maks_zbir_sredina;
for (int i = s+1; i <= d; i++) {
zbir_sredina += a[i];
if (zbir_sredina > maks_zbir_sredina)
maks_zbir_sredina = zbir_sredina;
}
return max({maks_zbir_levo, maks_zbir_desno,
maks_zbir_sredina});
}
int maksZbirSegmenta(const vector<int>& a) {
return maksZbirSegmenta(a, 0, a.size() - 1);
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maksZbirSegmenta(const vector<int>& a, int l, int d) {
if (l > d)
return 0;
int s = l + (d - l) / 2;
int maks_zbir_levo = maksZbirSegmenta(a, l, s-1);
int maks_zbir_desno = maksZbirSegmenta(a, s+1, d);
int zbir_sredina = a[s];
int maks_zbir_sredina = zbir_sredina;
for (int i = s-1; i >= l; i--) {
zbir_sredina += a[i];
if (zbir_sredina > maks_zbir_sredina)
maks_zbir_sredina = zbir_sredina;
}
zbir_sredina = maks_zbir_sredina;
for (int i = s+1; i <= d; i++) {
zbir_sredina += a[i];
if (zbir_sredina > maks_zbir_sredina)
maks_zbir_sredina = zbir_sredina;
}
return max({maks_zbir_levo, maks_zbir_desno,
maks_zbir_sredina});
}
int maksZbirSegmenta(const vector<int>& a) {
return maksZbirSegmenta(a, 0, a.size() - 1);
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << maksZbirSegmenta(a) << endl;
return 0;
}Ako sa \(n\) označimo dužinu niza \(d - l + 1\) i ako vreme izvršavanja obeležimo sa \(T(n)\), tada važi da je \(T(0) = O(1)\) i da je \(T(n) = 2T(n/2) + O(n)\). Naime, vrše se dva rekurzivna poziva za duplo manje nizove, a najveći zbir segmenata koji obuhvataju središnji element izračunavamo u vremenu \(O(n)\) (što je prilično očigledno, jer imamo dve petlje koje se ukupno izvršavaju \(n\) puta, a čija su tela konstantne složenosti). Na osnovu master teoreme lako se zaključuje da je \(T(n) = O(n \log{n})\). Dakle, ovaj algoritam je manje efikasan od algoritama složenosti \(O(n)\), ali je i dalje prilično upotrebljiv (i sigurno je mnogo bolji od algoritama grube sile koji su kvadratne ili kubne složenosti).
Na ideji dekompozicije možemo izgraditi i efikasniji algoritam. Ključni uvid je da se najveći zbir segmenta oko srednjeg elementa može dobiti kao zbir najvećeg sufiksa niza levo od tog elementa i najvećeg prefiksa niza desno od tog elementa. Možemo ojačati induktivnu hipotezu i umesto da prefiks i sufiks računamo u petlji, u linearnom vremenu, možemo pretpostaviti da za obe polovine niza prefiks i sufiks dobijamo kao rezultat rekurzivnog poziva. To nam je dovoljno da odredimo maksimalni zbir funkcije, ali moramo ,,vratiti dug’’ i naša funkcija sada pored maksimalnog zbira segmenta mora izračunati i maksimalni zbir prefiksa i maksimalni zbir sufiksa celog niza. Maksimalni zbir prefiksa celog niza je veći broj od maksimalnog zbira prefiksa levog dela i od zbira celog levog dela i maksimalnog zbira prefiksa desnog dela. Slično, maksimalni zbir sufiksa celog niza je veći od maksimalnog zbira sufiksa desnog dela i od zbira maksimalnog zbira sufiksa levog dela i celog desnog dela. Zato je neophodno dodatno ojačati induktivnu hipotezu i tokom rekurzije računati i zbir celog niza.
Pretpostavimo da je \(P\) zbir maksimalnog prefiksa niza, da je \(S\) zbir maksimalnog sufiksa niza, da je \(Z\) zbir celog niza i da je \(M\) maksimalni zbir segmenta niza. Označimo indeksom \(l\) te statistike u levoj polovini niza i indeksom \(d\) te statistke u desnoj polovini niza. Tada važi:
\[\begin{eqnarray*} Z &=& Z_l + Z_d\\ P &=& \max(P_l, Z_l + P_d)\\ S &=& \max(S_d, S_l + Z_d)\\ M &=& \max(M_l, M_d, S_l + P_d) \end{eqnarray*}\]
Jednačina koja opisuje ovu rekurziju je \(T(n) = 2T(n/2) + O(1)\), pa je složenost ovog rešenja linearna tj. \(O(n)\).
void maksZbirSegmenta(const vector<int>& a, int l, int d,
int& zbir, int& maks_zbir,
int& maks_prefiks, int& maks_sufiks) {
if (l == d) {
zbir = maks_zbir = maks_prefiks = maks_sufiks = a[l];
return;
}
int s = l + (d - l) / 2;
int zbir_levo, maks_zbir_levo,
maks_sufiks_levo, maks_prefiks_levo;
maksZbirSegmenta(a, l, s,
zbir_levo, maks_zbir_levo,
maks_prefiks_levo, maks_sufiks_levo);
int zbir_desno, maks_zbir_desno,
maks_sufiks_desno, maks_prefiks_desno;
maksZbirSegmenta(a, s+1, d,
zbir_desno, maks_zbir_desno,
maks_prefiks_desno, maks_sufiks_desno);
zbir = zbir_levo + zbir_desno;
maks_prefiks = max(maks_prefiks_levo,
zbir_levo + maks_prefiks_desno);
maks_sufiks = max(maks_sufiks_desno,
maks_sufiks_levo + zbir_desno);
maks_zbir = max({maks_zbir_levo, maks_zbir_desno,
maks_sufiks_levo + maks_prefiks_desno});
}
int maksZbirSegmenta(const vector<int>& a) {
int zbir, maks_zbir, maks_prefiks, maks_sufiks;
maksZbirSegmenta(a, 0, a.size() - 1,
zbir, maks_zbir, maks_prefiks, maks_sufiks);
return maks_zbir;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void maksZbirSegmenta(const vector<int>& a, int l, int d,
int& zbir, int& maks_zbir,
int& maks_prefiks, int& maks_sufiks) {
if (l == d) {
zbir = maks_zbir = maks_prefiks = maks_sufiks = a[l];
return;
}
int s = l + (d - l) / 2;
int zbir_levo, maks_zbir_levo,
maks_sufiks_levo, maks_prefiks_levo;
maksZbirSegmenta(a, l, s,
zbir_levo, maks_zbir_levo,
maks_prefiks_levo, maks_sufiks_levo);
int zbir_desno, maks_zbir_desno,
maks_sufiks_desno, maks_prefiks_desno;
maksZbirSegmenta(a, s+1, d,
zbir_desno, maks_zbir_desno,
maks_prefiks_desno, maks_sufiks_desno);
zbir = zbir_levo + zbir_desno;
maks_prefiks = max(maks_prefiks_levo,
zbir_levo + maks_prefiks_desno);
maks_sufiks = max(maks_sufiks_desno,
maks_sufiks_levo + zbir_desno);
maks_zbir = max({maks_zbir_levo, maks_zbir_desno,
maks_sufiks_levo + maks_prefiks_desno});
}
int maksZbirSegmenta(const vector<int>& a) {
int zbir, maks_zbir, maks_prefiks, maks_sufiks;
maksZbirSegmenta(a, 0, a.size() - 1,
zbir, maks_zbir, maks_prefiks, maks_sufiks);
return maks_zbir;
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << maksZbirSegmenta(a) << endl;
return 0;
}