streamalism.org

1. Pregled

Problem s maksimalnim podnizom zadatak je pronaći niz susjednih elemenata s maksimalnim zbrojem u bilo kojem danom nizu.

Na primjer, u donjem nizu, označena podskupina ima maksimalni zbroj (6):

U ovom ćemo tutorijalu pogledati dva rješenja za pronalaženje maksimalnog niza u nizu. Jednu od kojih ćemo dizajnirati Na) složenost vremena i prostora.

2. Algoritam grube sile

Gruba sila je iterativni pristup rješavanju problema. U većini slučajeva rješenje zahtijeva brojne iteracije nad strukturom podataka. U sljedećih nekoliko odjeljaka primijenit ćemo ovaj pristup da bismo riješili problem maksimalnog niza.

2.1. Pristup

Općenito govoreći, prvo rješenje koje vam padne na pamet je izračunati zbroj svih mogućih podmreža i vratiti onaj s maksimalnim zbrojem.

Za početak ćemo izračunati zbroj svake podloške koja započinje indeksom 0. I slično, pronaći ćemo sve podsklopove počevši od svakog indeksa od 0 do n-1 gdje n je duljina niza:

Pa ćemo početi s indeksa 0 i dodajte svaki element tekućem zbroju u iteraciji. Također ćemo vodite evidenciju o dosad viđenom maksimalnom zbroju. Ova je iteracija prikazana na lijevoj strani gornje slike.

Na desnoj strani slike možemo vidjeti iteraciju koja započinje indeksom 3. U posljednjem dijelu ove slike imamo podniz s maksimalnim zbrojem između indeksa 3 i 6.

Međutim, naš će algoritam i dalje nalaziti sve podsklopove počevši od indeksa između 0 i n-1.

2.2. Provedba

Pogledajmo sada kako ovo rješenje možemo implementirati u Javi:

javni int maxSubArray (int [] nums) {int n = nums.length; int maximumSubArraySum = Integer.MIN_VALUE; int početak = 0; int kraj = 0; for (int left = 0; left <n; left ++) {int runningWindowSum = 0; za (int desno = lijevo; desno maximumSubArraySum) {maximumSubArraySum = runningWindowSum; start = lijevo; kraj = desno; }}} logger.info ("Pronađen maksimalan podniz između {} i {}", početak, kraj); vrati maximumSubArraySum; }

Kao što se i očekivalo, ažuriramo maximumSubArraySum ako je trenutni zbroj veći od prethodnog maksimalnog zbroja. Značajno, tada također ažuriramo početak i kraj kako bismo saznali mjesta indeksa ovog podniza.

2.3. Složenost

Općenito govoreći, otopina grube sile ponavlja se preko niza mnogo puta kako bi se dobilo svako moguće rješenje. To znači da vrijeme potrebno ovom rješenju raste kvadratno s brojem elemenata u polju. To možda neće predstavljati problem za nizove male veličine. No kako veličina polja raste, ovo rješenje nije učinkovito.

Pregledom koda možemo vidjeti i da su dva ugniježđena za petlje. Stoga možemo zaključiti da je vremenska složenost ovog algoritma O (n2).

U kasnijim odjeljcima taj ćemo problem riješiti u Na) složenost korištenjem dinamičkog programiranja.

3. Dinamičko programiranje

Dinamičko programiranje rješava problem dijeljenjem na manje podprobleme. Ovo je vrlo slično tehnici rješavanja algoritma podijeli i osvoji. Međutim, glavna je razlika u tome što dinamičko programiranje potproblem rješava samo jednom.

Zatim pohranjuje rezultat ovog podproblema i kasnije ponovno koristi taj rezultat za rješavanje ostalih povezanih podproblema. Taj je postupak poznat pod nazivom memoizacija.

3.1. Kadaneov algoritam

Kadaneov algoritam je popularno rješenje problema s maksimalnim podnizom i temelji se na dinamičkom programiranju.

Najvažniji izazov u rješavanju dinamičkog programiranja problem je pronaći optimalne podprobleme.

3.2. Pristup

Shvatimo ovaj problem na drugačiji način:

Na gornjoj slici pretpostavljamo da maksimalni podskup završava na zadnjem mjestu indeksa. Prema tome, maksimalni zbroj podniza bit će:

maximumSubArraySum = max_so_far + arr [n-1]

max_so_far je maksimalni zbroj podniza koji završava indeksom n-2. To je također prikazano na gornjoj slici.

Sada ovu pretpostavku možemo primijeniti na bilo koji indeks u nizu. Na primjer, maksimalni zbroj podreda koji završava na n-2 može se izračunati kao:

maximumSubArraySum [n-2] = max_so_far [n-3] + arr [n-2]

Stoga možemo zaključiti da:

maximumSubArraySum [i] = maximumSubArraySum [i-1] + arr [i]

Sada, budući da je svaki element u polju poseban podniz veličine jedan, također moramo provjeriti je li element veći od maksimalnog zbroja:

maximumSubArraySum [i] = Max (arr [i], maximumSubArraySum [i-1] + arr [i])

Gledajući ove jednadžbe, možemo vidjeti da trebamo pronaći maksimalni zbroj niza kod svakog indeksa niza. Stoga smo svoj problem podijelili na n potproblemi. Maksimalni zbroj možemo pronaći u svakom indeksu ponavljanjem niza samo jednom:

Označeni element prikazuje trenutni element u iteraciji. Za svaki indeks primijenit ćemo jednadžbu izvedenu ranije kako bismo izračunali vrijednost za max_ending_here. To nam pomaže u identificiranju da li bismo trebali uključiti trenutni element u podniz ili započeti novi pod niz, počevši od ovog indeksa.

Druga varijabla, max_so_far koristi se za pohranu maksimalnog zbroja podreda koji je pronađen tijekom iteracije. Jednom kad ponovimo zadnji indeks, max_so_far pohranit će zbroj maksimalnog podniza.

3.3. Provedba

Ponovno, pogledajmo kako sada možemo implementirati Kadane algoritam u Javi, slijedeći gornji pristup:

javni int maxSubArraySum (int [] arr) {int veličina = arr.length; int početak = 0; int kraj = 0; int maxSoFar = 0, maxEndingHere = 0; for (int i = 0; i maxEndingHere + arr [i]) {start = i; maxEndingHere = arr [i]; } else maxEndingHere = maxEndingHere + arr [i]; if (maxSoFar <maxEndingHere) {maxSoFar = maxEndingHere; kraj = i; }} logger.info ("Pronađen maksimalan podniz između {} i {}", početak, kraj); povratak maxSoFar; }

Ovdje smo ažurirali početak i kraj kako bi se pronašli maksimalni indeksi podreda.

3.4. Složenost

Budući da polje moramo ponoviti samo jednom, vremenska složenost ovog algoritma je Na).

Dakle, kao što vidimo, vrijeme potrebno ovom rješenju raste linearno s brojem elemenata u nizu. Slijedom toga, učinkovitiji je od pristupa grube sile o kojem smo govorili u prošlom odjeljku.

4. Zaključak

U ovom smo brzom vodiču opisali dva načina za rješavanje problema s maksimalnim brojem podreda.

Prvo smo istražili pristup grube sile i vidjeli da je ovo iterativno rješenje rezultiralo kvadratnim vremenom. Kasnije smo zatim razgovarali o algoritmu Kadane i koristili dinamičko programiranje za rješavanje problema u linearnom vremenu.

Kao i uvijek, puni izvorni kôd članka dostupan je na GitHub-u.