Maximum Sub-Array Problem je rovnaké ako Maximum Slice Problem. Tento tutoriál pojednáva o probléme s kódovaním v C++. Otázka znie: aký je maximálny súčet akejkoľvek možnej postupnosti po sebe idúcich čísel v rámci poľa? To môže znamenať celé pole. Tento problém a jeho riešenie v akomkoľvek jazyku sa označuje ako Maximum Sub-Array Problem. Pole môže mať možné záporné čísla.
Riešenie musí byť efektívne. Musí mať čo najrýchlejšiu časovú zložitosť. Odteraz je najrýchlejší algoritmus riešenia vo vedeckej komunite známy ako Kadane's Algorithm. Tento článok vysvetľuje Kadaneov algoritmus s C++.
Príklady údajov
Zvážte nasledujúci vektor (pole):
vektor < int > A = { 5 , - 7 , 3 , 5 , - dva , 4 , - 1 } ;
Výsek (podpole) s maximálnym súčtom je sekvencia {3, 5, -2, 4}, ktorá dáva súčet 10. Žiadna iná možná sekvencia, dokonca ani celé pole, nedá súčet až hodnotu 10. Celé pole dáva súčet 7, čo nie je maximálny súčet.
Zvážte nasledujúci vektor:
vektor < int > B = { - dva , 1 , - 3 , 4 , - 1 , dva , 1 , - 5 , 4 } ;
Výsek (podpole) s maximálnym súčtom je sekvencia {4, −1, 2, 1}, ktorá dáva súčet 6. Všimnite si, že v rámci podpola môžu byť záporné čísla pre maximálny súčet.
Zvážte nasledujúci vektor:
vektor < int > C = { 3 , dva , - 6 , 4 , 0 } ;
Výsek (podpole) s maximálnym súčtom je sekvencia {3, 2}, ktorá dáva súčet 5.
Zvážte nasledujúci vektor:
vektor < int > D = { 3 , dva , 6 , - 1 , 4 , 5 , - 1 , dva } ;
Podpole s maximálnym súčtom je postupnosť, {3, 2, 6, -1, 4, 5, -1, 2}, ktorá dáva súčet 20. Je to celé pole.
Zvážte nasledujúci vektor:
vektor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , pätnásť , 4 , - 8 , - pätnásť , - 22 } ;
Tu sú dve čiastkové polia s maximálnymi súčtami. Vyšší súčet je ten, ktorý sa považuje za riešenie (odpoveď) pre maximálny problém podpolia. Čiastkové polia sú: {5, 7} so súčtom 12 a {6, 5, 10, -5, 15, 4} so súčtom 35. Samozrejme, segment so súčtom 35 je odpoveď.
Zvážte nasledujúci vektor:
vektor < int > F = { - 4 , 10 , pätnásť , 9 , - 5 , - dvadsať , - 3 , - 12 , - 3 , 4 , 6 , 3 , dva , 8 , 3 , - 5 , - dva } ;
Existujú dve čiastkové polia s maximálnymi súčtami. Vyšší súčet je ten, ktorý sa považuje za riešenie pre maximálny problém podpolia. Čiastkové polia sú: {10, 15, 9} so súčtom 34 a {4, 6, 3, 2, 8, 3} so súčtom 26. Výsek so súčtom 34 je samozrejme odpoveď, pretože problém je hľadať podpole s najvyšším súčtom a nie podpole s vyššou sumou.
Vývoj Kadaneovho algoritmu
Informácie v tejto časti tutoriálu nie sú pôvodným dielom z Kadane. Je to autorov vlastný spôsob, ako naučiť Kadaneov algoritmus. Jeden z vyššie uvedených vektorov s jeho priebežnými súčtami je v tejto tabuľke:
| Údaje | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | pätnásť | 4 | -8 | - pätnásť | -22 |
| Priebežný súčet | 5 | 12 | 8 | -dva | -8 | -dva | 3 | 13 | 8 | 23 | 27 | dvadsaťjeden | 16 | -6 |
| index | 0 | 1 | dva | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | jedenásť | 12 | 13 |
Priebežný súčet pre index je súčet všetkých predchádzajúcich hodnôt vrátane hodnôt pre index. Sú tu dve sekvencie s maximálnymi súčtami. Sú to {5, 7}, čo dáva súčet 12, a {6, 5, 10, -5, 15, 4}, čo dáva súčet 35. Požadovaná je postupnosť, ktorá dáva súčet 35 .
Všimnite si, že pre priebežné súčty existujú dva vrcholy, ktoré predstavujú hodnoty, 12 a 27. Tieto vrcholy zodpovedajú posledným indexom týchto dvoch sekvencií.
Myšlienkou Kadaneovho algoritmu je teda robiť priebežný súčet pri porovnávaní maximálnych súm tak, ako sa vyskytujú, pričom sa v danom poli pohybujú zľava doprava.
Ďalší vektor zhora s priebežnými súčtami je v tejto tabuľke:
Existujú dve sekvencie s maximálnymi súčtami. Sú to {10, 15, 9}, čo dáva súčet 34; a {4, 6, 3, 2, 8, 3}, čo dáva súčet 26. Požadovaná je postupnosť, ktorá dáva súčet 34.
Všimnite si, že pre priebežné súčty existujú dva vrcholy, ktoré predstavujú hodnoty, 30 a 13. Tieto vrcholy zodpovedajú posledným indexom dvoch sekvencií.
Myšlienkou Kadaneovho algoritmu je opäť robiť priebežný súčet pri porovnávaní maximálnych súm tak, ako sa vyskytujú, pričom sa v danom poli pohybujú zľava doprava.
Kód podľa Kadaneovho algoritmu v C++
Kód uvedený v tejto časti článku nie je nevyhnutne tým, čo použil Kadane. Je to však podľa jeho algoritmu. Program ako mnoho iných programov v C++ by začínal takto:
#include#include
pomocou menného priestoru std;
Je tu zahrnutá knižnica iostream, ktorá je zodpovedná za vstup a výstup. Používa sa štandardný menný priestor.
Myšlienkou Kadaneovho algoritmu je mať priebežný súčet pri porovnávaní maximálnych súm, ktoré sa vyskytujú pri pohybe zľava doprava v danom poli. Funkcia pre algoritmus je:
int maxSunArray ( vektor < int > & A ) {int N = A.veľkosť ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
pre ( int i = 1 ; i < N; i++ ) {
int tempRunTotal = runTotal + A [ i ] ; // môže byť menšia ako A [ i ]
ak ( A [ i ] > tempRunTotal )
runTotal = A [ i ] ; // v prípad A [ i ] je väčší ako bežiaci súčet
inak
runTotal = tempRunTotal;
ak ( runTotal > maxAmount ) // porovnanie všetkých maximálnych súm
maxSum = runTotal;
}
vrátiť maxAmount;
}
Určí sa veľkosť, N daného poľa (vektora). Premenná maxSum je jedným z možných maximálnych súm. Pole má aspoň jeden maximálny súčet. Premenná runTotal predstavuje priebežný súčet pri každom indexe. Obe sú inicializované prvou hodnotou poľa. Ak je v tomto algoritme nasledujúca hodnota v poli väčšia ako priebežný súčet, potom sa nasledujúca hodnota stane novým priebežným súčtom.
Existuje jedna hlavná slučka for. Skenovanie začína od 1 a nie od nuly kvôli inicializácii premenných, maxSum a runTotal na A[0], čo je prvý prvok daného poľa.
V slučke for určuje prvý príkaz dočasný priebežný súčet pridaním aktuálnej hodnoty k akumulovanému súčtu všetkých predchádzajúcich hodnôt.
Ďalej je tu konštrukcia if/else. Ak je samotná aktuálna hodnota väčšia ako doterajší priebežný súčet, potom sa táto jednotlivá hodnota stane priebežným súčtom. To je užitočné najmä vtedy, ak sú všetky hodnoty v danom poli záporné. V tomto prípade sa samotná najvyššia záporná hodnota stane maximálnou hodnotou (odpoveď). Ak aktuálna hodnota sama o sebe nie je väčšia ako doterajší dočasný priebežný súčet, potom sa priebežný súčet stane predchádzajúcim priebežným súčtom plus aktuálna hodnota – toto je iná časť konštrukcie if/else.
Posledný segment kódu v slučke for volí medzi akýmkoľvek predchádzajúcim maximálnym súčtom pre predchádzajúcu sekvenciu (podpole) a akýmkoľvek aktuálnym maximálnym súčtom pre aktuálnu sekvenciu. Preto sa zvolí vyššia hodnota. Môže existovať viac ako jeden maximálny súčet čiastkových polí. Všimnite si, že priebežný súčet by stúpal a klesal, pretože pole sa skenuje zľava doprava. Klesá, keď spĺňa záporné hodnoty.
Konečná zvolená maximálna suma čiastkového poľa sa vráti po slučke for.
Obsah vhodnej hlavnej funkcie C++ pre funkciu Kadaneovho algoritmu 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 , pätnásť , 4 , - 8 , - pätnásť , - 22 } ; // { 6 , 5 , 10 , - 5 , pätnásť , 4 } - > 35
int ret5 = maxSunArray ( A ) ;
cout << ret5 << endl;
vektor < int > F = { - 4 , 10 , pätnásť , 9 , - 5 , - dvadsať , - 3 , - 12 , - 3 , 4 , 6 , 3 , dva , 8 , 3 , - 5 , - dva } ; // { 10 , pätnásť , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << vpravo 6 << endl;
Vďaka tomu bude výstup:
10
6
5
dvadsať
35
3. 4
Každá odpoveď v tomto riadku zodpovedá danému poli v poradí.
Záver
Časová zložitosť pre Kadaneov algoritmus je O(n), kde n je počet prvkov v danom poli. Táto časová zložitosť je najrýchlejšia pre problém maximálneho podpolia. Existujú aj iné algoritmy, ktoré sú pomalšie. Myšlienkou Kadaneovho algoritmu je robiť priebežný súčet a zároveň porovnávať maximálne sumy tak, ako sa vyskytujú, pričom sa v danom poli pohybujú zľava doprava. Ak je samotná aktuálna hodnota väčšia ako doterajší priebežný súčet, potom sa táto jediná hodnota stane novým priebežným súčtom. V opačnom prípade je nový priebežný súčet predchádzajúci priebežný súčet plus aktuálny prvok, ako sa očakávalo pri skenovaní daného poľa.
Môže existovať viac ako jeden maximálny súčet pre rôzne možné čiastkové polia. Vyberie sa najvyšší maximálny súčet pre všetky možné čiastkové polia.
Aké sú obmedzujúce indexy pre rozsah zvoleného maximálneho súčtu? – To je diskusia na inokedy!
Chrys