Problem največje podmatrike je enak problemu največje rezine. Ta vadnica obravnava težavo s kodiranjem v C++. Vprašanje je: kakšna je največja vsota katerega koli možnega zaporedja zaporednih števil v matriki? To lahko pomeni celoten niz. Ta problem in njegova rešitev v katerem koli jeziku se imenuje problem maksimalne podmatrike. Matrika ima lahko možna negativna števila.
Rešitev mora biti učinkovita. Imeti mora najhitrejšo časovno zapletenost. Trenutno je najhitrejši algoritem za rešitev v znanstveni skupnosti znan kot Kadanov algoritem. Ta članek razlaga Kadanejev algoritem s C++.
Primeri podatkov
Razmislite o naslednjem vektorju (matriki):
vektor < int > A = { 5 , - 7 , 3 , 5 , - dva , 4 , - 1 } ;
Rezina (podmatrika) z največjo vsoto je zaporedje {3, 5, -2, 4}, ki daje vsoto 10. Nobeno drugo možno zaporedje, niti celotno polje, ne bo dalo vsote do vrednost 10. Celotna matrika daje vsoto 7, kar ni največja vsota.
Razmislite o naslednjem vektorju:
vektor < int > B = { - dva , 1 , - 3 , 4 , - 1 , dva , 1 , - 5 , 4 } ;
Rezina (podmatrika) z največjo vsoto je zaporedje {4, −1, 2, 1}, ki daje vsoto 6. Upoštevajte, da so znotraj podmatrike za največjo vsoto lahko negativna števila.
Razmislite o naslednjem vektorju:
vektor < int > C = { 3 , dva , - 6 , 4 , 0 } ;
Rezina (podmatrika) z največjo vsoto je zaporedje {3, 2}, ki daje vsoto 5.
Razmislite o naslednjem vektorju:
vektor < int > D = { 3 , dva , 6 , - 1 , 4 , 5 , - 1 , dva } ;
Podmatrika z največjo vsoto je zaporedje {3, 2, 6, -1, 4, 5, -1, 2}, ki daje vsoto 20. To je celotna matrika.
Razmislite o naslednjem vektorju:
vektor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , petnajst , 4 , - 8 , - petnajst , - 22 } ;
Tu sta dve podnizici z največjimi vsotami. Višja vsota je tista, ki se šteje kot rešitev (odgovor) za problem maksimalne podmatrike. Podnizi sta: {5, 7} z vsoto 12 in {6, 5, 10, -5, 15, 4} z vsoto 35. Seveda je rezina z vsoto 35 odgovor.
Razmislite o naslednjem vektorju:
vektor < int > F = { - 4 , 10 , petnajst , 9 , - 5 , - dvajset , - 3 , - 12 , - 3 , 4 , 6 , 3 , dva , 8 , 3 , - 5 , - dva } ;
Obstajata dve podnizici z največjimi vsotami. Višja vsota je tista, ki se obravnava kot rešitev za problem maksimalne podmatrike. Podmatri so: {10, 15, 9} z vsoto 34 in {4, 6, 3, 2, 8, 3} z vsoto 26. Seveda je rezina z vsoto 34 odgovor, ker je težava iskati podniz z najvišjo vsoto in ne podniz z višjo vsoto.
Razvijanje Kadanejevega algoritma
Informacije v tem razdelku vadnice niso izvirno delo Kadaneja. To je avtorjev način poučevanja Kadanovega algoritma. Eden od zgornjih vektorjev s tekočimi vsotami je v tej tabeli:
| podatki | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | petnajst | 4 | -8 | - petnajst | -22 |
| Tekoči seštevek | 5 | 12 | 8 | -dva | -8 | -dva | 3 | 13 | 8 | 23 | 27 | enaindvajset | 16 | -6 |
| kazalo | 0 | 1 | dva | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | enajst | 12 | 13 |
Tekoča vsota za indeks je vsota vseh prejšnjih vrednosti, vključno s tisto za indeks. Tukaj sta dve zaporedji z največjimi vsotami. To sta {5, 7}, kar daje vsoto 12, in {6, 5, 10, -5, 15, 4}, kar daje vsoto 35. Zaporedje, ki daje vsoto 35, je želeno .
Upoštevajte, da sta za tekoče vsote dva vrha, ki sta vrednosti, 12 in 27. Ti vrhovi ustrezajo zadnjima indeksoma obeh zaporedij.
Ideja Kadanejevega algoritma je torej, da izračuna tekočo vsoto, medtem ko primerja največje vsote, ko se srečajo, in se premika od leve proti desni v danem nizu.
Še en vektor od zgoraj s tekočimi vsotami je v tej tabeli:
Obstajata dve zaporedji z največjimi vsotami. So {10, 15, 9}, kar daje vsoto 34; in {4, 6, 3, 2, 8, 3}, kar daje vsoto 26. Zaporedje, ki daje vsoto 34, je želeno.
Upoštevajte, da sta za tekoče vsote dva vrha, ki sta vrednosti, 30 in 13. Ti vrhovi ustrezajo zadnjima indeksoma obeh zaporedij.
Ideja Kadanejevega algoritma je tudi ta, da izračuna tekočo vsoto, medtem ko primerja največje vsote, ko se srečajo, in se premika od leve proti desni v danem nizu.
Koda s Kadanejevim algoritmom v C++
Koda, navedena v tem delu članka, ni nujno tisto, kar je uporabil Kadane. Vendar pa je po njegovem algoritmu. Program, kot mnogi drugi programi C++, bi se začel z:
#include#vključi
uporaba imenskega prostora std;
Vključena je knjižnica iostream, ki je odgovorna za vnos in izhod. Uporabljen je standardni imenski prostor.
Zamisel Kadanejevega algoritma je imeti tekočo vsoto, medtem ko primerja najvišje vsote, ko se nanje naletijo, premikanje od leve proti desni v danem nizu. Funkcija za algoritem je:
int maxSunArray ( vektor < int > & A ) {int N = A.size ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
za ( int jaz = 1 ; jaz < N; i++ ) {
int tempRunTotal = runTotal + A [ jaz ] ; // lahko manjši od A [ jaz ]
če ( A [ jaz ] > tempRunTotal )
runTotal = A [ jaz ] ; // v Ovitek A [ jaz ] je večji od skupnega zneska
drugače
runTotal = tempRunTotal;
če ( runTotal > maxAmount ) // primerjava vseh največjih vsot
maxSum = runTotal;
}
vrnitev maxAmount;
}
Določi se velikost N danega niza (vektorja). Spremenljivka maxSum je ena od možnih največjih vsot. Matrika ima vsaj eno največjo vsoto. Spremenljivka runTotal predstavlja tekočo vsoto pri vsakem indeksu. Oba sta inicializirana s prvo vrednostjo matrike. Če je v tem algoritmu naslednja vrednost v matriki večja od tekoče vsote, bo naslednja vrednost postala nova tekoča vsota.
Obstaja ena glavna for-zanka. Pregledovanje se začne od 1 in ne od nič zaradi inicializacije spremenljivk maxSum in runTotal v A[0], ki je prvi element dane matrike.
V zanki for prvi stavek določi začasno tekočo vsoto tako, da doda trenutno vrednost akumulirani vsoti vseh prejšnjih vrednosti.
Nato sledi konstrukt if/else. Če je samo trenutna vrednost večja od dosedanje tekoče vsote, potem ta posamezna vrednost postane tekoča vsota. To je priročno, zlasti če so vse vrednosti v dani matriki negativne. V tem primeru bo samo največja negativna vrednost postala največja vrednost (odgovor). Če samo trenutna vrednost ni večja od dosedanje začasne tekoče vsote, postane tekoča vsota prejšnja tekoča vsota plus trenutna vrednost – to je else-del konstrukcije if/else.
Zadnji segment kode v zanki for izbira med katero koli prejšnjo najvišjo vsoto za prejšnje zaporedje (podmatriko) in katero koli trenutno največjo vsoto za trenutno zaporedje. Zato je izbrana višja vrednost. Obstaja lahko več kot ena največja vsota podmatric. Upoštevajte, da bi tekoča vsota naraščala in padala, ko se polje skenira od leve proti desni. Pade, ko se sreča z negativnimi vrednostmi.
Končno izbrana največja vsota podmatric se vrne po for-zanki.
Vsebina za ustrezno glavno funkcijo C++ za funkcijo Kadanejevega 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 , petnajst , 4 , - 8 , - petnajst , - 22 } ; // { 6 , 5 , 10 , - 5 , petnajst , 4 } - > 35
int ret5 = maxSunArray ( IN ) ;
cout << ret5 << endl;
vektor < int > F = { - 4 , 10 , petnajst , 9 , - 5 , - dvajset , - 3 , - 12 , - 3 , 4 , 6 , 3 , dva , 8 , 3 , - 5 , - dva } ; // { 10 , petnajst , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << desno 6 << endl;
S tem bo rezultat:
10
6
5
dvajset
35
3. 4
Vsaka vrstica odgovora tukaj ustreza dani matriki po vrstnem redu.
Zaključek
Časovna kompleksnost za Kadanejev algoritem je O(n), kjer je n število elementov v danem nizu. Ta časovna zapletenost je najhitrejša za problem maksimalne podmatrike. Obstajajo tudi drugi algoritmi, ki so počasnejši. Zamisel Kadanejevega algoritma je, da izračuna tekočo vsoto, medtem ko primerja največje vsote, ko se nanje naleti, in se premika od leve proti desni v danem nizu. Če je samo trenutna vrednost večja od dosedanje tekoče vsote, potem ta posamezna vrednost postane nova tekoča vsota. V nasprotnem primeru je nova tekoča vsota prejšnja tekoča vsota plus trenutni element, kot je bilo pričakovano, ko je dana matrika skenirana.
Obstaja lahko več kot ena največja vsota za različne možne podnize. Izbrana je najvišja največja vsota za vse možne podnize.
Kakšni so mejni indeksi za območje izbrane maksimalne vsote? – To je razprava za kdaj drugič!
Chrys