Suurin alataulukko -ongelma on sama kuin Suurin siivuongelma. Tässä opetusohjelmassa käsitellään C++:n koodauksen ongelmaa. Kysymys kuuluu: mikä on taulukossa olevien peräkkäisten lukujen maksimisumma? Tämä voi tarkoittaa koko joukkoa. Tätä ongelmaa ja sen ratkaisua millä tahansa kielellä kutsutaan Maximum Sub-Array -ongelmaksi. Taulukossa voi olla mahdollisia negatiivisia lukuja.
Ratkaisun on oltava tehokas. Sillä on oltava nopein aikamonimutkaisuus. Toistaiseksi nopein ratkaisun algoritmi tunnetaan tiedeyhteisössä nimellä Kadanen algoritmi. Tämä artikkeli selittää Kadanen algoritmin C++:lla.
Esimerkkejä tiedoista
Harkitse seuraavaa vektoria (taulukko):
vektori < int > A = { 5 ,- 7 , 3 , 5 ,- kaksi , 4 ,- 1 } ;
Suurimman summan omaava siivu (alitaulukko) on sekvenssi {3, 5, -2, 4}, joka antaa summan 10. Mikään muu mahdollinen sekvenssi, edes koko matriisi, ei anna summaa enintään arvo 10. Koko taulukko antaa summan 7, joka ei ole suurin summa.
Harkitse seuraavaa vektoria:
vektori < int > B = { - kaksi , 1 ,- 3 , 4 ,- 1 , kaksi , 1 ,- 5 , 4 } ;
Suurimman summan sisältävä viipale (alitaulukko) on sekvenssi {4, −1, 2, 1}, joka antaa summan 6. Huomaa, että alitaulukossa voi olla negatiivisia lukuja maksimisumman saamiseksi.
Harkitse seuraavaa vektoria:
vektori < int > C = { 3 , kaksi ,- 6 , 4 , 0 } ;
Viipale (alitaulukko), jolla on suurin summa, on sekvenssi {3, 2}, joka antaa summan 5.
Harkitse seuraavaa vektoria:
vektori < int > D = { 3 , kaksi , 6 ,- 1 , 4 , 5 ,- 1 , kaksi } ;
Suurimman summan omaava alitaulukko on sekvenssi {3, 2, 6, -1, 4, 5, -1, 2}, joka antaa summan 20. Se on koko taulukko.
Harkitse seuraavaa vektoria:
vektori < int > E = { 5 , 7 ,- 4 ,- 10 ,- 6 , 6 , 5 , 10 ,- 5 , viisitoista , 4 ,- 8 ,- viisitoista ,- 22 } ;
Tässä on kaksi alitaulukkoa, joissa on enimmäissummat. Suurempi summa on se, jota pidetään suurimman alitaulukon ongelman ratkaisuna (vastauksena). Alitaulukot ovat: {5, 7} summalla 12 ja {6, 5, 10, -5, 15, 4} summalla 35. Tietenkin siivu, jonka summa on 35, on vastaus.
Harkitse seuraavaa vektoria:
vektori < int > F = { - 4 , 10 , viisitoista , 9 ,- 5 ,- kaksikymmentä ,- 3 ,- 12 ,- 3 , 4 , 6 , 3 , kaksi , 8 , 3 ,- 5 ,- kaksi } ;
On olemassa kaksi alitaulukkoa, joissa on enimmäissummat. Suurempi summa on se, jota pidetään suurimman alitaulukon ongelman ratkaisuna. Alitaulukot ovat: {10, 15, 9} summalla 34 ja {4, 6, 3, 2, 8, 3} summalla 26. Tietenkin siivu, jonka summa on 34, on vastaus, koska ongelmana on etsiä alitaulukkoa, jolla on suurin summa, eikä alitaulukkoa, jonka summa on suurempi.
Kadanen algoritmin kehittäminen
Tämän opetusohjelman osan tiedot eivät ole alkuperäisiä Kadanen töitä. Se on kirjoittajan oma tapa opettaa Kadanen algoritmia. Yksi yllä olevista vektoreista juoksevine kokonaismäärineen on tässä taulukossa:
| Data | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | viisitoista | 4 | -8 | -viisitoista | -22 |
| Juoksu yhteensä | 5 | 12 | 8 | -kaksi | -8 | -kaksi | 3 | 13 | 8 | 23 | 27 | kaksikymmentäyksi | 16 | -6 |
| indeksi | 0 | 1 | kaksi | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | yksitoista | 12 | 13 |
Indeksin suoritettava summa on kaikkien aiempien arvojen summa, mukaan lukien indeksin arvo. Tässä on kaksi sekvenssiä, joissa on enimmäissummat. Ne ovat {5, 7}, joka antaa summan 12, ja {6, 5, 10, -5, 15, 4}, joka antaa summan 35. Jakso, joka antaa summan 35, on se, mitä halutaan .
Huomaa, että juoksevilla summilla on kaksi huippua, jotka ovat arvot, 12 ja 27. Nämä huiput vastaavat kahden sekvenssin viimeisiä indeksejä.
Joten, Kadanen algoritmin ideana on tehdä juokseva kokonaissumma samalla kun verrataan maksimisummaa, kun niitä kohdataan, liikkuen vasemmalta oikealle annetussa taulukossa.
Toinen ylhäältä tuleva vektori juoksevine kokonaistuloksineen on tässä taulukossa:
On kaksi jaksoa, joissa on enimmäissummat. Ne ovat {10, 15, 9}, mikä antaa summan 34; ja {4, 6, 3, 2, 8, 3}, joka antaa summan 26. Sejono, joka antaa summan 34, on se, mitä halutaan.
Huomaa, että juoksevilla kokonaissummalla on kaksi huippua, jotka ovat arvot, 30 ja 13. Nämä huiput vastaavat kahden sekvenssin viimeisiä indeksejä.
Jälleen, Kadanen algoritmin ideana on tehdä juoksusumma samalla kun verrataan maksimisummaa, kun ne kohtaavat, liikkuen vasemmalta oikealle annetussa taulukossa.
Koodi Kadanen algoritmilla C++:ssa
Artikkelin tässä osassa annettu koodi ei välttämättä ole sitä, mitä Kadane käytti. Se on kuitenkin hänen algoritminsa mukaan. Ohjelma, kuten monet muut C++-ohjelmat, alkaisi seuraavasti:
#include#sisällytä
käyttäen nimiavaruutta std;
Mukana on iostream-kirjasto, joka vastaa syötöstä ja lähdöstä. Käytetään vakionimiavaruutta.
Kadanen algoritmin ideana on saada juoksevaa summaa samalla kun verrataan maksimisummaa, kun niitä kohdataan, liikkuen vasemmalta oikealle annetussa taulukossa. Algoritmin funktio on:
int maxSunArray ( vektori < int > & A ) {int N = A.koko ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
varten ( int i = 1 ; i < N; i++ ) {
int tempRunTotal = runTotal + A [ i ] ; // voi olla pienempi kuin A [ i ]
jos ( A [ i ] > tempRunTotal )
runTotal = A [ i ] ; // sisään tapaus A [ i ] on suurempi kuin juoksu yhteensä
muu
runTotal = tempRunTotal;
jos ( runTotal > maxAmount ) // vertaamalla kaikkia enimmäissummia
maxSum = runTotal;
}
palata maxAmount;
}
Määritetään annetun taulukon (vektorin) koko, N. Muuttuja maxSum on yksi mahdollisista maksimisummaista. Taulukossa on vähintään yksi maksimisumma. Muuttuja runTotal edustaa juoksevaa kokonaismäärää kussakin indeksissä. Ne molemmat alustetaan taulukon ensimmäisellä arvolla. Tässä algoritmissa, jos taulukon seuraava arvo on suurempi kuin juokseva kokonaissumma, seuraavasta arvosta tulee uusi juoksusumma.
On yksi pääfor-silmukka. Skannaus alkaa 1:stä eikä nollasta, koska muuttujat maxSum ja runTotal on alustettu arvoon A[0], joka on annetun taulukon ensimmäinen elementti.
For-silmukassa ensimmäinen lause määrittää väliaikaisen juoksevan summan lisäämällä nykyisen arvon kaikkien aiempien arvojen kumuloituneeseen summaan.
Seuraavaksi on if/else-konstruktio. Jos nykyinen arvo yksin on suurempi kuin juokseva kokonaismäärä tähän mennessä, tästä yksittäisestä arvosta tulee juokseva kokonaismäärä. Tämä on kätevää varsinkin, jos kaikki annetun taulukon arvot ovat negatiivisia. Tässä tapauksessa korkeimmasta negatiivisesta arvosta tulee yksin maksimiarvo (vastaus). Jos nykyinen arvo ei yksin ole suurempi kuin väliaikainen juoksusumma tähän mennessä, juoksevasta kokonaissummasta tulee edellinen juokseva kokonaissumma plus nykyinen arvo – tämä if/else-konstruktion else-osa.
For-silmukan viimeinen koodisegmentti valitsee edellisen sekvenssin (alitaulukon) aiemman maksimisumman ja nykyisen sekvenssin minkä tahansa nykyisen maksimisumman välillä. Tästä syystä valitaan suurempi arvo. Suurin alitaulukon summa voi olla useampi kuin yksi. Huomaa, että juokseva kokonaissumma nousee ja laskee, kun taulukkoa skannataan vasemmalta oikealle. Se putoaa, kun se täyttää negatiiviset arvot.
Lopullinen valittu enimmäisalitaulukon summa palautetaan for-silmukan jälkeen.
Sopivan C++-pääfunktion sisältö Kadanen algoritmifunktiolle on:
vektori < int > A = { 5 ,- 7 , 3 , 5 ,- kaksi , 4 ,- 1 } ; // { 3 , 5 ,- kaksi , 4 } - > 10int ret1 = maxSunArray ( A ) ;
cout << ret1 << endl;
vektori < int > B = { - kaksi , 1 ,- 3 , 4 ,- 1 , kaksi , 1 ,- 5 , 4 } ; // { 4 , − 1 , kaksi , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << endl;
vektori < int > C = { 3 , kaksi ,- 6 , 4 , 0 } ; // { 3 , kaksi } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << endl;
vektori < int > D = { 3 , kaksi , 6 ,- 1 , 4 , 5 ,- 1 , kaksi } ; // { 3 , kaksi , 6 ,- 1 , 4 , 5 ,- 1 , kaksi } - > 5
int ret4 = maxSunArray ( D ) ;
cout << net4 << endl;
vektori < int > E = { 5 , 7 ,- 4 ,- 10 ,- 6 , 6 , 5 , 10 ,- 5 , viisitoista , 4 ,- 8 ,- viisitoista ,- 22 } ; // { 6 , 5 , 10 ,- 5 , viisitoista , 4 } - > 35
int ret5 = maxSunArray ( JA ) ;
cout << ret5 << endl;
vektori < int > F = { - 4 , 10 , viisitoista , 9 ,- 5 ,- kaksikymmentä ,- 3 ,- 12 ,- 3 , 4 , 6 , 3 , kaksi , 8 , 3 ,- 5 ,- kaksi } ; // { 10 , viisitoista , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << oikea 6 << endl;
Sen avulla tulos on:
10
6
5
kaksikymmentä
35
3. 4
Jokainen rivin vastaus tässä vastaa tiettyä taulukkoa, järjestyksessä.
Johtopäätös
Kadanen algoritmin aikamonimutkaisuus on O(n), missä n on elementtien lukumäärä annetussa taulukossa. Tämä aikamonimutkaisuus on nopein suurimmalle alitaulukon ongelmalle. On muitakin algoritmeja, jotka ovat hitaampia. Kadanen algoritmin ideana on tehdä juokseva kokonaissumma, samalla kun verrataan maksimisummaa, kun niitä kohdataan, liikkuen annetussa taulukossa vasemmalta oikealle. Jos nykyinen arvo yksin on suurempi kuin juokseva kokonaismäärä tähän mennessä, tästä yksittäisestä arvosta tulee uusi juoksusumma. Muussa tapauksessa uusi juoksusumma on edellinen juokseva kokonaissumma plus nykyinen elementti, kuten oletetaan, kun annettua taulukkoa tarkistetaan.
Eri mahdollisille alitaulukoille voi olla useampi kuin yksi maksimisumma. Suurin maksimisumma kaikille mahdollisille alitaulukoille valitaan.
Mitkä ovat valitun maksimisumman alueen rajoittavat indeksit? – Se on keskustelua toisen kerran!
Chrys