A Maximum Sub-Array Probléma megegyezik a Maximum Slice Problémával. Ez az oktatóanyag a C++ kódolással kapcsolatos problémát tárgyalja. A kérdés a következő: mennyi lehet a lehetséges egymást követő számsorozatok maximális összege egy tömbön belül? Ez jelentheti az egész tömböt. Ezt a problémát és megoldását bármely nyelven Maximum Sub-Array Problémának nevezik. A tömbben lehetnek negatív számok.
A megoldásnak hatékonynak kell lennie. A leggyorsabb időbonyolításnak kell lennie. Jelenleg a megoldás leggyorsabb algoritmusa Kadane algoritmusaként ismert a tudományos közösségben. Ez a cikk elmagyarázza Kadane algoritmusát C++ nyelven.
Adatpéldák
Tekintsük a következő vektort (tömböt):
vektor < int > A = { 5 , - 7 , 3 , 5 , - két , 4 , - 1 } ;
A maximális összegű szelet (altömb) a sorozat, {3, 5, -2, 4}, amely 10-es összeget ad. Semmilyen más lehetséges sorozat, még az egész tömb sem ad max. Az egész tömb 7-et ad, ami nem a maximális összeg.
Tekintsük a következő vektort:
vektor < int > B = { - két , 1 , - 3 , 4 , - 1 , két , 1 , - 5 , 4 } ;
A maximális összegű szelet (altömb) a {4, −1, 2, 1} sorozat, amely 6 összeget ad. Vegye figyelembe, hogy az altömbön belül lehetnek negatív számok a maximális összeg érdekében.
Tekintsük a következő vektort:
vektor < int > C = { 3 , két , - 6 , 4 , 0 } ;
A maximális összegű szelet (altömb) a {3, 2} sorozat, amely 5 összeget ad.
Tekintsük a következő vektort:
vektor < int > D = { 3 , két , 6 , - 1 , 4 , 5 , - 1 , két } ;
A maximális összegű résztömb a {3, 2, 6, -1, 4, 5, -1, 2} sorozat, amely 20 összeget ad. Ez a teljes tömb.
Tekintsük a következő vektort:
vektor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , tizenöt , 4 , - 8 , - tizenöt , - 22 } ;
Itt két altömb van maximális összegekkel. A nagyobb összeg az, amelyet a maximális résztömb probléma megoldásának (válaszának) tekintünk. Az altömbök a következők: {5, 7} 12 összeggel és {6, 5, 10, -5, 15, 4} 35 összeggel. Természetesen a 35 összegű szelet a válasz.
Tekintsük a következő vektort:
vektor < int > F = { - 4 , 10 , tizenöt , 9 , - 5 , - húsz , - 3 , - 12 , - 3 , 4 , 6 , 3 , két , 8 , 3 , - 5 , - két } ;
Két altömb van maximális összegekkel. A nagyobb összeget tekintjük a maximális résztömb probléma megoldásának. Az altömbök a következők: {10, 15, 9} 34 összeggel és {4, 6, 3, 2, 8, 3} 26 összeggel. Természetesen a 34 összegű szelet a válasz, mert az a probléma, hogy a legnagyobb összegű altömböt kell keresni, és nem a nagyobb összegű altömböt.
Kadane algoritmusának fejlesztése
Az oktatóanyag ezen részében található információk nem a Kadane eredeti munkái. A szerző saját módszere a Kadane-algoritmus tanítására. A fenti vektorok egyike a futó összegekkel ebben a táblázatban található:
| Adat | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | tizenöt | 4 | -8 | -tizenöt | -22 |
| Futó Összesen | 5 | 12 | 8 | -két | -8 | -két | 3 | 13 | 8 | 23 | 27 | huszonegy | 16 | -6 |
| index | 0 | 1 | két | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | tizenegy | 12 | 13 |
Az index futásának összege az összes előző érték összege, beleértve az index értékét is. Itt két sorozat van maximális összegekkel. Ezek a következők: {5, 7}, amely 12 összeget ad, és {6, 5, 10, -5, 15, 4}, amely 35 összeget ad. A 35-öt adó sorozat a kívánt .
Figyeljük meg, hogy a futó összegeknél két csúcs van, ezek a 12 és 27. Ezek a csúcsok a két sorozat utolsó indexének felelnek meg.
Tehát a Kadane-algoritmusnak az az ötlete, hogy az adott tömbben balról jobbra haladva végezze el a futó összeget, miközben összehasonlítja a maximális összegeket.
Egy másik vektor felülről a futó összegekkel ebben a táblázatban található:
Két sorozat van maximális összegekkel. Ezek {10, 15, 9}, ami 34-et ad; és {4, 6, 3, 2, 8, 3}, amely 26-ot ad. A 34 összegét adó sorozat a kívánt.
Figyeljük meg, hogy a futó összegeknél két csúcs van, ezek a 30 és 13. Ezek a csúcsok a két sorozat utolsó indexének felelnek meg.
A Kadane-algoritmus ötlete ismét az, hogy a futó összesítést végezze el, miközben összehasonlítja a maximális összegeket, amikor találkoznak, balról jobbra haladva az adott tömbben.
A Kadane-algoritmus kódja C++ nyelven
A cikk ezen részében megadott kód nem feltétlenül az, amit Kadane használt. Ez azonban az ő algoritmusa szerint történik. A program sok más C++ programhoz hasonlóan így kezdődik:
#include#include
névtér használata std;
Beleértve az iostream könyvtárat, amely a bemenetért és a kimenetért felelős. A szabványos névteret használjuk.
Kadane algoritmusának az az ötlete, hogy az adott tömbben balról jobbra haladva, legyen a futó végösszeg, miközben összehasonlítja a maximális összegeket. Az algoritmus függvénye:
int maxSunArray ( vektor < int > & A ) {int N = A.méret ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
számára ( int én = 1 ; én < N; i++ ) {
int tempRunTotal = runTotal + A [ én ] ; // kisebb lehet, mint A [ én ]
ha ( A [ én ] > tempRunTotal )
runTotal = A [ én ] ; // ban ben ügy A [ én ] nagyobb, mint a futó összesen
más
runTotal = tempRunTotal;
ha ( runTotal > maxAmount ) // az összes maximális összeget összehasonlítva
maxSum = runTotal;
}
Visszatérés maxAmount;
}
Meghatározzuk az adott tömb (vektor) N méretét. A maxSum változó a lehetséges maximális összegek egyike. Egy tömbnek legalább egy maximális összege van. A runTotal változó az egyes indexeknél futó összeget jelenti. Mindkettő a tömb első értékével inicializálódik. Ebben az algoritmusban, ha a tömb következő értéke nagyobb, mint a futó összeg, akkor a következő érték lesz az új futó összeg.
Van egy fő for-hurok. A szkennelés 1-től kezdődik és nem nullától, mert a maxSum és a runTotal változók A[0]-ra inicializálódnak, ami az adott tömb első eleme.
A for-ciklusban az első utasítás ideiglenes futó összeget határoz meg úgy, hogy az aktuális értéket hozzáadja az összes előző érték összesített összegéhez.
Ezután van egy if/else konstrukció. Ha az aktuális érték önmagában nagyobb, mint az eddigi futó végösszeg, akkor ez az egyetlen érték lesz a futó végösszeg. Ez különösen akkor hasznos, ha az adott tömbben minden érték negatív. Ebben az esetben egyedül a legmagasabb negatív érték lesz a maximális érték (a válasz). Ha az aktuális érték önmagában nem nagyobb, mint az eddigi ideiglenes futó végösszeg, akkor a futó végösszeg lesz az előző futó összeg plusz az aktuális érték – ez az if/else konstrukció else-része.
A for-ciklus utolsó kódszegmense választhat egy korábbi sorozat (altömb) korábbi maximális összege és az aktuális sorozat bármely aktuális maximális összege között. Ezért a magasabb értéket választjuk. Egynél több maximális résztömb összege lehet. Vegye figyelembe, hogy a futó végösszeg emelkedik és csökken, amikor a tömb balról jobbra halad. Úgy esik, ahogy negatív értékeket talál.
A végső kiválasztott maximális résztömb összege a for-ciklus után kerül visszaadásra.
A megfelelő C++ főfüggvény tartalma a Kadane algoritmus függvényéhez:
vektor < int > A = { 5 , - 7 , 3 , 5 , - két , 4 , - 1 } ; // { 3 , 5 , - két , 4 } - > 10int ret1 = maxSunArray ( A ) ;
cout << ret1 << endl;
vektor < int > B = { - két , 1 , - 3 , 4 , - 1 , két , 1 , - 5 , 4 } ; // { 4 , − 1 , két , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << endl;
vektor < int > C = { 3 , két , - 6 , 4 , 0 } ; // { 3 , két } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << endl;
vektor < int > D = { 3 , két , 6 , - 1 , 4 , 5 , - 1 , két } ; // { 3 , két , 6 , - 1 , 4 , 5 , - 1 , két } - > 5
int ret4 = maxSunArray ( D ) ;
cout << net4 << endl;
vektor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , tizenöt , 4 , - 8 , - tizenöt , - 22 } ; // { 6 , 5 , 10 , - 5 , tizenöt , 4 } - > 35
int ret5 = maxSunArray ( ÉS ) ;
cout << ret5 << endl;
vektor < int > F = { - 4 , 10 , tizenöt , 9 , - 5 , - húsz , - 3 , - 12 , - 3 , 4 , 6 , 3 , két , 8 , 3 , - 5 , - két } ; // { 10 , tizenöt , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << jobb 6 << endl;
Ezzel a kimenet a következő lesz:
10
6
5
húsz
35
3. 4
Minden sor válasz itt, egy adott tömbnek felel meg, sorrendben.
Következtetés
A Kadane-algoritmus időbonyolultsága O(n), ahol n az adott tömb elemeinek száma. Ez az időbonyolultság a leggyorsabb a maximális résztömb probléma esetén. Vannak más algoritmusok is, amelyek lassabbak. Kadane algoritmusának az az ötlete, hogy a futó összesítést elvégezzük, miközben az adott tömbben balról jobbra haladva összehasonlítjuk a maximális összegeket. Ha az aktuális érték önmagában nagyobb, mint az eddigi futó összeg, akkor ez az egyetlen érték lesz az új futó összeg. Ellenkező esetben az új futó összeg az előző futó összeg plusz az aktuális elem, ahogy az várható volt, az adott tömb vizsgálatakor.
Egynél több maximális összeg lehet a különböző lehetséges altömbökhöz. Az összes lehetséges altömb legmagasabb maximális összege kerül kiválasztásra.
Melyek a korlátozó indexek a kiválasztott maximális összeg tartományára? – Ez egy másik alkalomra szóló vita!
Chrys