Maksimaalne alammassiivi probleem on sama, mis maksimaalse lõigu probleem. Selles õpetuses käsitletakse C++-i kodeerimise probleemi. Küsimus on: kui suur on massiivi võimalike järjestikuste arvude jada maksimaalne summa? See võib tähendada kogu massiivi. Seda probleemi ja selle lahendust mis tahes keeles nimetatakse maksimaalse alammassiivi probleemiks. Massiivil võivad olla negatiivsed arvud.
Lahendus peab olema tõhus. Sellel peab olema kiireim ajaline keerukus. Praeguse seisuga on lahenduse kiireim algoritm teadusringkondades tuntud kui Kadane'i algoritm. See artikkel selgitab Kadane'i algoritmi C++-ga.
Andmete näited
Vaatleme järgmist vektorit (massiivi):
vektor < int > A = { 5 ,- 7 , 3 , 5 ,- kaks , 4 ,- 1 } ;
Maksimaalse summaga viil (alamsiiv) on jada {3, 5, -2, 4}, mis annab summaks 10. Ükski teine võimalik jada, isegi kogu massiiv, ei anna summat kuni väärtus 10. Kogu massiiv annab summaks 7, mis ei ole maksimaalne summa.
Mõelge järgmisele vektorile:
vektor < int > B = { - kaks , 1 ,- 3 , 4 ,- 1 , kaks , 1 ,- 5 , 4 } ;
Maksimaalse summaga viil (alamsiiv) on jada {4, −1, 2, 1}, mis annab summaks 6. Pange tähele, et alammassiivis võib maksimaalse summa saamiseks olla negatiivseid arve.
Mõelge järgmisele vektorile:
vektor < int > C = { 3 , kaks ,- 6 , 4 , 0 } ;
Maksimaalse summaga viil (alamsiiv) on jada {3, 2}, mis annab summaks 5.
Mõelge järgmisele vektorile:
vektor < int > D = { 3 , kaks , 6 ,- 1 , 4 , 5 ,- 1 , kaks } ;
Maksimaalse summaga alammassiiviks on jada {3, 2, 6, -1, 4, 5, -1, 2}, mis annab summaks 20. See on kogu massiiv.
Mõelge järgmisele vektorile:
vektor < int > E = { 5 , 7 ,- 4 ,- 10 ,- 6 , 6 , 5 , 10 ,- 5 , viisteist , 4 ,- 8 ,- viisteist ,- 22 } ;
Siin on kaks maksimaalsete summadega alammassiivi. Suurem summa on see, mida peetakse maksimaalse alammassiivi ülesande lahenduseks (vastuseks). Alammassiivid on: {5, 7} summaga 12 ja {6, 5, 10, -5, 15, 4} summaga 35. Muidugi on lõigud summaga 35 vastus.
Mõelge järgmisele vektorile:
vektor < int > F = { - 4 , 10 , viisteist , 9 ,- 5 ,- kakskümmend ,- 3 ,- 12 ,- 3 , 4 , 6 , 3 , kaks , 8 , 3 ,- 5 ,- kaks } ;
Maksimaalsete summadega on kaks alammassiivi. Suurem summa on see, mida peetakse maksimaalse alammassiivi probleemi lahenduseks. Alammassiivid on: {10, 15, 9} summaga 34 ja {4, 6, 3, 2, 8, 3} summaga 26. Muidugi on lõigud summaga 34 vastus, sest probleem on otsida suurima summaga alammassiivi ja mitte suurema summaga alammassiivi.
Kadane'i algoritmi väljatöötamine
Selles õpetuse jaotises olev teave ei ole Kadane originaalteos. See on autori enda viis Kadane'i algoritmi õpetada. Üks ülaltoodud vektoritest koos jooksvate kogusummadega on selles tabelis:
| Andmed | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | viisteist | 4 | -8 | - viisteist | -22 |
| Jooksu kokku | 5 | 12 | 8 | - kaks | -8 | - kaks | 3 | 13 | 8 | 23 | 27 | kakskümmend üks | 16 | -6 |
| indeks | 0 | 1 | kaks | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | üksteist | 12 | 13 |
Indeksi kogusumma on kõigi eelmiste väärtuste summa, sealhulgas indeksi väärtus. Siin on kaks maksimaalse summaga jada. Need on {5, 7}, mis annab summaks 12, ja {6, 5, 10, -5, 15, 4}, mis annab summaks 35. Jada, mis annab summaks 35, on see, mida soovitakse .
Pange tähele, et jooksvate kogusummade jaoks on kaks tippu, mille väärtused on 12 ja 27. Need piigid vastavad kahe jada viimastele indeksitele.
Niisiis, Kadane'i algoritmi idee on teha jooksev kogusumma, samal ajal võrreldes maksimaalseid summasid, kui need kokku puutuvad, liikudes antud massiivi vasakult paremale.
Teine vektor ülalt koos jooksvate kogusummadega on selles tabelis:
Maksimaalse summaga jada on kaks. Need on {10, 15, 9}, mis annab summaks 34; ja {4, 6, 3, 2, 8, 3}, mis annab summaks 26. Jada, mis annab summa 34, on see, mida soovitakse.
Pange tähele, et jooksvate kogusummade jaoks on kaks tippu, mille väärtused on 30 ja 13. Need piigid vastavad kahe jada viimastele indeksidele.
Jällegi, Kadane'i algoritmi idee on teha jooksev kogusumma, samal ajal kui võrrelda maksimaalseid summasid, kui need kokku puutuvad, liikudes antud massiivi vasakult paremale.
Kadane'i algoritmi kood C++ keeles
Artikli selles jaotises antud kood ei pruugi olla see, mida Kadane kasutas. Kuid see on tema algoritmi järgi. Programm, nagu paljud teised C++ programmid, algaks järgmisega:
#include#kaasa
kasutades nimeruumi std;
Seal on kaasatud iostream teek, mis vastutab sisendi ja väljundi eest. Kasutatakse standardset nimeruumi.
Kadane'i algoritmi idee on omada jooksvat kogusummat, samas võrrelda maksimaalseid summasid, kui need kokku puutuvad, liikudes antud massiivi vasakult paremale. Algoritmi funktsioon on:
int maxSunArray ( vektor < int > & A ) {int N = A.suurus ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
jaoks ( int i = 1 ; i < N; i++ ) {
int tempRunTotal = runTotal + A [ i ] ; // võib olla väiksem kui A [ i ]
kui ( A [ i ] > tempRunTotal )
runTotal = A [ i ] ; // sisse juhtum A [ i ] on suurem kui jooksmine kokku
muidu
runTotal = tempRunTotal;
kui ( runTotal > maxAmount ) // kõigi maksimumsummade võrdlemine
maxSum = runTotal;
}
tagasi maxAmount;
}
Määratakse antud massiivi (vektori) suurus N. Muutuja maxSum on üks võimalikest maksimumsummadest. Massiivil on vähemalt üks maksimaalne summa. Muutuja runTotal tähistab iga indeksi jooksvat kogusummat. Mõlemad lähtestatakse massiivi esimese väärtusega. Selle algoritmi puhul, kui massiivi järgmine väärtus on suurem jooksvast kogusummast, saab sellest järgmisest väärtusest uus jooksev kogusumma.
Seal on üks peamine for-silmus. Skaneerimine algab 1-st, mitte nullist, kuna muutujad maxSum ja runTotal initsialiseeritakse väärtuseks A[0], mis on antud massiivi esimene element.
For-tsüklis määrab esimene lause ajutise jooksva kogusumma, lisades praeguse väärtuse kõigi eelmiste väärtuste akumuleeritud summale.
Järgmiseks on if/else konstruktsioon. Kui ainuüksi praegune väärtus on suurem kui seni jooksev kogusumma, saab sellest üksikust väärtusest jooksev kogusumma. See on mugav, eriti kui kõik antud massiivi väärtused on negatiivsed. Sel juhul saab suurimast negatiivsest väärtusest üksi maksimaalne väärtus (vastus). Kui praegune väärtus üksi ei ole suurem kui seni ajutine jooksev kogusumma, saab jooksvast kogusummast eelmine jooksev kogusumma pluss praegune väärtus – see on if/else konstruktsiooni else-osa.
For-tsükli viimane koodisegment valib eelmise jada (alamsiivu) eelneva maksimumsumma ja praeguse jada mis tahes praeguse maksimumsumma vahel. Seetõttu valitakse kõrgem väärtus. Maksimaalset alammassiivi summat võib olla rohkem kui üks. Pange tähele, et jooksev kogusumma tõuseb ja langeb, kuna massiivi skannitakse vasakult paremale. See langeb, kui see vastab negatiivsetele väärtustele.
Lõplik valitud maksimaalne alammassiivi summa tagastatakse pärast for-tsüklit.
Sobiva C++ põhifunktsiooni sisu Kadane algoritmi funktsiooni jaoks on:
vektor < int > A = { 5 ,- 7 , 3 , 5 ,- kaks , 4 ,- 1 } ; // { 3 , 5 ,- kaks , 4 } - > 10int ret1 = maxSunArray ( A ) ;
cout << ret1 << endl;
vektor < int > B = { - kaks , 1 ,- 3 , 4 ,- 1 , kaks , 1 ,- 5 , 4 } ; // { 4 , − 1 , kaks , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << endl;
vektor < int > C = { 3 , kaks ,- 6 , 4 , 0 } ; // { 3 , kaks } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << endl;
vektor < int > D = { 3 , kaks , 6 ,- 1 , 4 , 5 ,- 1 , kaks } ; // { 3 , kaks , 6 ,- 1 , 4 , 5 ,- 1 , kaks } - > 5
int ret4 = maxSunArray ( D ) ;
cout << net4 << endl;
vektor < int > E = { 5 , 7 ,- 4 ,- 10 ,- 6 , 6 , 5 , 10 ,- 5 , viisteist , 4 ,- 8 ,- viisteist ,- 22 } ; // { 6 , 5 , 10 ,- 5 , viisteist , 4 } - > 35
int ret5 = maxSunArray ( JA ) ;
cout << ret5 << endl;
vektor < int > F = { - 4 , 10 , viisteist , 9 ,- 5 ,- kakskümmend ,- 3 ,- 12 ,- 3 , 4 , 6 , 3 , kaks , 8 , 3 ,- 5 ,- kaks } ; // { 10 , viisteist , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << õige 6 << endl;
Sellega on väljund järgmine:
10
6
5
kakskümmend
35
3. 4
Iga rea vastus siin vastab antud massiivile, järjekorras.
Järeldus
Kadane'i algoritmi ajaline keerukus on O(n), kus n on antud massiivi elementide arv. See ajaline keerukus on maksimaalse alammassiivi probleemi jaoks kiireim. On ka teisi aeglasemaid algoritme. Kadane'i algoritmi idee on teha jooksev kogusumma, samas võrrelda maksimaalseid summasid, kui need kokku puutuvad, liikudes antud massiivi vasakult paremale. Kui ainuüksi praegune väärtus on suurem kui seni jooksev kogusumma, saab sellest üksikust väärtusest uus jooksev kogusumma. Vastasel juhul on uus jooksev kogusumma eelmine jooksev kogusumma pluss praegune element, nagu etteantud massiivi kontrollimisel.
Erinevate võimalike alammassiivide jaoks võib olla rohkem kui üks maksimaalne summa. Kõigi võimalike alammassiivide jaoks valitakse suurim maksimaalne summa.
Millised on valitud maksimumsumma vahemiku piiravad indeksid? – See on arutelu mõneks muuks ajaks!
Chrys