Problem maksimalnog podniza isti je kao problem maksimalnog odsječka. Ovaj vodič govori o problemu kodiranja u C++. Pitanje je: koji je najveći zbroj bilo kojeg mogućeg niza uzastopnih brojeva unutar niza? To može značiti cijeli niz. Ovaj problem i njegovo rješenje u bilo kojem jeziku se naziva problem maksimalnog podniza. Niz može sadržavati moguće negativne brojeve.
Rješenje mora biti učinkovito. Mora imati najbržu vremensku složenost. Za sada je najbrži algoritam za rješenje poznat u znanstvenoj zajednici kao Kadaneov algoritam. Ovaj članak objašnjava Kadaneov algoritam s C++.
Primjeri podataka
Razmotrimo sljedeći vektor (niz):
vektor < int > A = { 5 , - 7 , 3 , 5 , - dva , 4 , - 1 } ;
Isječak (podniz) s maksimalnim zbrojem je slijed, {3, 5, -2, 4}, koji daje zbroj od 10. Nijedan drugi mogući slijed, čak ni cijeli niz, neće dati zbroj do vrijednost 10. Cijeli niz daje zbroj 7, što nije najveći zbroj.
Razmotrimo sljedeći vektor:
vektor < int > B = { - dva , 1 , - 3 , 4 , - 1 , dva , 1 , - 5 , 4 } ;
Odsječak (podniz) s maksimalnim zbrojem je niz {4, −1, 2, 1} koji daje zbroj 6. Imajte na umu da unutar podniza za maksimalan zbroj mogu biti negativni brojevi.
Razmotrimo sljedeći vektor:
vektor < int > C = { 3 , dva , - 6 , 4 , 0 } ;
Isječak (podniz) s maksimalnim zbrojem je niz, {3, 2} koji daje zbroj 5.
Razmotrimo sljedeći vektor:
vektor < int > D = { 3 , dva , 6 , - 1 , 4 , 5 , - 1 , dva } ;
Podniz s najvećim zbrojem je niz {3, 2, 6, -1, 4, 5, -1, 2} koji daje zbroj 20. To je cijeli niz.
Razmotrimo sljedeći vektor:
vektor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , petnaest , 4 , - 8 , - petnaest , - 22 } ;
Ovdje postoje dva podniza s maksimalnim zbrojem. Veći zbroj je onaj koji se smatra rješenjem (odgovorom) za problem maksimalnog podniza. Podnizovi su: {5, 7} sa zbrojem 12 i {6, 5, 10, -5, 15, 4} sa zbrojem 35. Naravno, isječak sa zbrojem 35 je odgovor.
Razmotrimo sljedeći vektor:
vektor < int > F = { - 4 , 10 , petnaest , 9 , - 5 , - dvadeset , - 3 , - 12 , - 3 , 4 , 6 , 3 , dva , 8 , 3 , - 5 , - dva } ;
Postoje dva podniza s maksimalnim zbrojevima. Veći zbroj je onaj koji se smatra rješenjem problema maksimalnog podniza. Podnizovi su: {10, 15, 9} sa zbrojem 34 i {4, 6, 3, 2, 8, 3} sa zbrojem 26. Naravno, odsječak sa zbrojem 34 je odgovor jer je problem tražiti podniz s najvećim zbrojem, a ne podniz s većim zbrojem.
Razvijanje Kadaneovog algoritma
Informacije u ovom odjeljku vodiča nisu izvorni Kadaneov rad. To je autorov vlastiti način podučavanja Kadaneovog algoritma. Jedan od gornjih vektora, sa svojim tekućim ukupnim iznosima, nalazi se u ovoj tablici:
| Podaci | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | petnaest | 4 | -8 | -petnaest | -22 |
| Ukupno | 5 | 12 | 8 | -dva | -8 | -dva | 3 | 13 | 8 | 23 | 27 | dvadeset i jedan | 16 | -6 |
| indeks | 0 | 1 | dva | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | jedanaest | 12 | 13 |
Tekući ukupni zbroj za indeks je zbroj svih prethodnih vrijednosti uključujući onu za indeks. Ovdje postoje dva niza s maksimalnim zbrojem. To su {5, 7}, što daje zbroj 12, i {6, 5, 10, -5, 15, 4}, što daje zbroj 35. Niz koji daje zbroj 35 je ono što se želi .
Primijetite da za tekuće ukupne vrijednosti postoje dva vrha koji su vrijednosti, 12 i 27. Ovi vrhovi odgovaraju zadnjim indeksima dva niza.
Dakle, ideja Kadaneovog algoritma je izračunavanje tekućeg zbroja dok se maksimalni zbrojevi uspoređuju kako se naiđu, krećući se slijeva nadesno u zadanom nizu.
Još jedan vektor odozgo, sa svojim tekućim ukupnim iznosima, nalazi se u ovoj tablici:
Postoje dva niza s maksimalnim zbrojem. Oni su {10, 15, 9}, što daje zbroj od 34; i {4, 6, 3, 2, 8, 3} što daje zbroj 26. Niz koji daje zbroj 34 je ono što se želi.
Primijetite da za tekuće ukupne vrijednosti postoje dva vrha koji su vrijednosti, 30 i 13. Ovi vrhovi odgovaraju zadnjim indeksima dva niza.
Opet, ideja Kadaneovog algoritma je izračunavanje tekućeg zbroja dok se maksimalni zbrojevi uspoređuju kako se naiđu, krećući se slijeva nadesno u zadanom nizu.
Kodiranje Kadaneovim algoritmom u C++
Kod naveden u ovom odjeljku članka nije nužno ono što je Kadane koristio. Međutim, to je po njegovom algoritmu. Program, kao i mnogi drugi C++ programi, počinje s:
#include#uključi
korištenje imenskog prostora std;
Tu je uključena biblioteka iostream, koja je odgovorna za ulaz i izlaz. Koristi se standardni imenski prostor.
Ideja Kadaneovog algoritma je imati tekući ukupni iznos dok uspoređuje maksimalne iznose kako se naiđu, pomičući se slijeva nadesno u zadanom nizu. Funkcija za algoritam je:
int maxSunArray ( vektor < int > i A ) {int N = A.veličina ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
za ( int ja = 1 ; ja < N; i++ ) {
int tempRunTotal = runTotal + A [ ja ] ; // može biti manji od A [ ja ]
ako ( A [ ja ] > tempRunTotal )
runTotal = A [ ja ] ; // u slučaj A [ ja ] je veći od tekućeg ukupnog broja
drugo
runTotal = tempRunTotal;
ako ( runTotal > maxAmount ) // uspoređujući sve maksimalne sume
maxSum = runTotal;
}
povratak maxAmount;
}
Određuje se veličina N zadanog niza (vektora). Varijabla maxSum jedna je od mogućih maksimalnih suma. Niz ima najmanje jedan maksimalni zbroj. Varijabla runTotal predstavlja tekući ukupni iznos za svaki indeks. Oba su inicijalizirana s prvom vrijednošću niza. U ovom algoritmu, ako je sljedeća vrijednost u nizu veća od tekućeg ukupnog iznosa, tada će ta sljedeća vrijednost postati novi tekući ukupni iznos.
Postoji jedna glavna for-petlja. Skeniranje počinje od 1, a ne od nule zbog inicijalizacije varijabli, maxSum i runTotal u A[0] koji je prvi element zadanog niza.
U for-petlji, prva izjava određuje privremenu tekuću ukupnu vrijednost dodavanjem trenutne vrijednosti akumuliranom zbroju svih prethodnih vrijednosti.
Zatim, tu je if/else konstrukcija. Ako je samo trenutna vrijednost veća od tekućeg ukupnog iznosa do sada, ta pojedinačna vrijednost postaje tekući ukupni iznos. Ovo je zgodno posebno ako su sve vrijednosti u danom nizu negativne. U tom će slučaju samo najveća negativna vrijednost postati najveća vrijednost (odgovor). Ako samo trenutna vrijednost nije veća od privremenog tekućeg ukupnog iznosa do sada, tada tekući ukupni iznos postaje prethodni tekući ukupni iznos plus trenutna vrijednost, – ovo je else dio if/else konstrukcije.
Posljednji segment koda u for-petlji bira između bilo kojeg prethodnog maksimalnog zbroja za prethodni niz (podniz) i bilo kojeg trenutnog maksimalnog zbroja za trenutni niz. Stoga je odabrana veća vrijednost. Može postojati više od jednog maksimalnog zbroja podniza. Imajte na umu da će tekući ukupni iznos rasti i padati, dok se polje skenira slijeva na desno. Pada kada naiđe na negativne vrijednosti.
Konačni odabrani maksimalni zbroj podniza vraća se nakon for-petlje.
Sadržaj za odgovarajuću C++ glavnu funkciju, za funkciju Kadaneovog algoritma je:
vektor < int > A = { 5 , - 7 , 3 , 5 , - dva , 4 , - 1 } ; // { 3 , 5 , - dva , 4 } - > 10int ret1 = maxSunArray ( A ) ;
cout << ret1 << endl;
vektor < int > B = { - dva , 1 , - 3 , 4 , - 1 , dva , 1 , - 5 , 4 } ; // { 4 , − 1 , dva , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << endl;
vektor < int > C = { 3 , dva , - 6 , 4 , 0 } ; // { 3 , dva } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << endl;
vektor < int > D = { 3 , dva , 6 , - 1 , 4 , 5 , - 1 , dva } ; // { 3 , dva , 6 , - 1 , 4 , 5 , - 1 , dva } - > 5
int ret4 = maxSunArray ( D ) ;
cout << net4 << endl;
vektor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , petnaest , 4 , - 8 , - petnaest , - 22 } ; // { 6 , 5 , 10 , - 5 , petnaest , 4 } - > 35
int ret5 = maxSunArray ( I ) ;
cout << ret5 << endl;
vektor < int > F = { - 4 , 10 , petnaest , 9 , - 5 , - dvadeset , - 3 , - 12 , - 3 , 4 , 6 , 3 , dva , 8 , 3 , - 5 , - dva } ; // { 10 , petnaest , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << desno 6 << endl;
Uz to, izlaz će biti:
10
6
5
dvadeset
35
3. 4
Svaki red odgovora ovdje, odgovara zadanom nizu, redom.
Zaključak
Vremenska složenost za Kadaneov algoritam je O(n), gdje je n broj elemenata u danom nizu. Ova vremenska složenost je najbrža za problem maksimalnog podniza. Postoje i drugi algoritmi koji su sporiji. Ideja Kadaneova algoritma je izračunavanje tekućeg zbroja, dok se maksimalni zbrojevi uspoređuju kako se naiđu, pomičući se slijeva nadesno u zadanom nizu. Ako je samo trenutna vrijednost veća od tekućeg ukupnog iznosa do sada, ta pojedinačna vrijednost postaje novi tekući ukupni iznos. U suprotnom, novi tekući zbroj je prethodni tekući zbroj plus trenutni element, kao što je predviđeno, dok se dani niz skenira.
Može postojati više od jednog maksimalnog zbroja za različite moguće podnizove. Odabire se najveći maksimalni zbroj za sve moguće podnizove.
Koji su granični indeksi za raspon odabranog maksimalnog zbroja? – To je rasprava za neki drugi put!
Chrys