Maximum Sub-Array Problem je stejné jako Maximum Slice Problem. Tento tutoriál pojednává o problému s kódováním v C++. Otázka zní: jaký je maximální součet jakékoli možné sekvence po sobě jdoucích čísel v poli? To může znamenat celé pole. Tento problém a jeho řešení v jakémkoli jazyce se nazývá Maximum Sub-Array Problem. Pole může mít možná záporná čísla.
Řešení musí být efektivní. Musí mít co nejrychlejší časovou složitost. V současné době je nejrychlejší algoritmus řešení známý ve vědecké komunitě jako Kadane's Algorithm. Tento článek vysvětluje Kadaneův algoritmus s C++.
Příklady dat
Zvažte následující vektor (pole):
vektor < int > A = { 5 ,- 7 , 3 , 5 ,- dva , 4 ,- 1 } ;
Řez (podpole) s maximálním součtem je posloupnost, {3, 5, -2, 4}, která dává součet 10. Žádná jiná možná posloupnost, ani celé pole, nedá součet až hodnota 10. Celé pole dává součet 7, což není maximální součet.
Zvažte následující vektor:
vektor < int > B = { - dva , 1 ,- 3 , 4 ,- 1 , dva , 1 ,- 5 , 4 } ;
Řez (dílčí pole) s maximálním součtem je posloupnost, {4, −1, 2, 1}, která dává součet 6. Všimněte si, že v rámci dílčího pole mohou být pro maximální součet záporná čísla.
Zvažte následující vektor:
vektor < int > C = { 3 , dva ,- 6 , 4 , 0 } ;
Řez (podpole) s maximálním součtem je sekvence {3, 2}, která dává součet 5.
Zvažte následující vektor:
vektor < int > D = { 3 , dva , 6 ,- 1 , 4 , 5 ,- 1 , dva } ;
Dílčí pole s maximálním součtem je sekvence {3, 2, 6, -1, 4, 5, -1, 2}, která dává součet 20. Je to celé pole.
Zvažte následující vektor:
vektor < int > E = { 5 , 7 ,- 4 ,- 10 ,- 6 , 6 , 5 , 10 ,- 5 , patnáct , 4 ,- 8 ,- patnáct ,- 22 } ;
Zde jsou dvě dílčí pole s maximálními součty. Vyšší součet je ten, který je považován za řešení (odpověď) pro problém maximálního dílčího pole. Dílčí pole jsou: {5, 7} se součtem 12 a {6, 5, 10, -5, 15, 4} se součtem 35. Řez se součtem 35 je samozřejmě odpověď.
Zvažte následující vektor:
vektor < int > F = { - 4 , 10 , patnáct , 9 ,- 5 ,- dvacet ,- 3 ,- 12 ,- 3 , 4 , 6 , 3 , dva , 8 , 3 ,- 5 ,- dva } ;
Existují dvě dílčí pole s maximálními součty. Vyšší součet je ten, který je považován za řešení problému maximálního dílčího pole. Dílčí pole jsou: {10, 15, 9} se součtem 34 a {4, 6, 3, 2, 8, 3} se součtem 26. Řez se součtem 34 je samozřejmě odpověď, protože problém je hledat podpole s nejvyšším součtem a ne podpole s vyšším součtem.
Vývoj Kadaneova algoritmu
Informace v této části tutoriálu nejsou původní prací z Kadane. Je to autorův vlastní způsob, jak naučit Kadaneův algoritmus. Jeden z výše uvedených vektorů s průběžnými součty je v této tabulce:
| Data | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | patnáct | 4 | -8 | -patnáct | -22 |
| Průběžný celkem | 5 | 12 | 8 | -dva | -8 | -dva | 3 | 13 | 8 | 23 | 27 | dvacet jedna | 16 | -6 |
| index | 0 | 1 | dva | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | jedenáct | 12 | 13 |
Průběžný součet pro index je součtem všech předchozích hodnot včetně hodnot pro index. Jsou zde dvě sekvence s maximálními součty. Jsou to {5, 7}, což dává součet 12, a {6, 5, 10, -5, 15, 4}, což dává součet 35. Požadovaná je posloupnost, která dává součet 35 .
Všimněte si, že pro průběžné součty existují dva píky, což jsou hodnoty, 12 a 27. Tyto píky odpovídají posledním indexům těchto dvou sekvencí.
Myšlenka Kadaneova algoritmu tedy spočívá v provádění průběžného součtu při porovnávání maximálních součtů, jak se vyskytují, a pohybují se v daném poli zleva doprava.
Další vektor shora s průběžnými součty je v této tabulce:
Existují dvě sekvence s maximálními součty. Jsou {10, 15, 9}, což dává součet 34; a {4, 6, 3, 2, 8, 3}, což dává součet 26. Posloupnost, která dává součet 34, je to, co je žádoucí.
Všimněte si, že pro průběžné součty existují dva píky, které jsou hodnotami, 30 a 13. Tyto píky odpovídají posledním indexům dvou sekvencí.
Opět platí, že myšlenkou Kadaneova algoritmu je provádět průběžný součet a zároveň porovnávat maximální součty tak, jak se vyskytují, a pohybovat se v daném poli zleva doprava.
Kód podle Kadane's Algorithm v C++
Kód uvedený v této části článku není nutně tím, co Kadane použil. Je to však podle jeho algoritmu. Program, stejně jako mnoho jiných programů C++, by začínal takto:
#include#include
pomocí jmenného prostoru std;
Je zde zahrnuta knihovna iostream, která je zodpovědná za vstup a výstup. Je použit standardní jmenný prostor.
Myšlenkou Kadaneova algoritmu je mít průběžný součet a zároveň porovnávat maximální součty tak, jak se vyskytují, a pohybovat se v daném poli zleva doprava. Funkce pro algoritmus je:
int maxSunArray ( vektor < int > & A ) {int N = A.velikost ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
pro ( int i = 1 ; i < N; i++ ) {
int tempRunTotal = runTotal + A [ i ] ; // může být menší než A [ i ]
-li ( A [ i ] > tempRunTotal )
runTotal = A [ i ] ; // v případ A [ i ] je větší než průběžný součet
jiný
runTotal = tempRunTotal;
-li ( runTotal > maxAmount ) // porovnání všech maximálních částek
maxSum = runTotal;
}
vrátit se maxAmount;
}
Určí se velikost, N daného pole (vektoru). Proměnná maxSum je jedním z možných maximálních součtů. Pole má alespoň jeden maximální součet. Proměnná runTotal představuje průběžný součet na každém indexu. Oba jsou inicializovány první hodnotou pole. V tomto algoritmu, pokud je další hodnota v poli větší než průběžný součet, pak se tato další hodnota stane novým průběžným součtem.
Existuje jedna hlavní smyčka for. Skenování začíná od 1 a ne od nuly kvůli inicializaci proměnných, maxSum a runTotal na A[0], což je první prvek daného pole.
Ve smyčce for určuje první příkaz dočasný průběžný součet přidáním aktuální hodnoty k akumulovanému součtu všech předchozích hodnot.
Dále je zde konstrukce if/else. Pokud je samotná aktuální hodnota větší než dosavadní průběžný součet, pak se tato jednotlivá hodnota stane průběžným součtem. To je užitečné zejména v případě, že všechny hodnoty v daném poli jsou záporné. V tomto případě se nejvyšší záporná hodnota sama stane maximální hodnotou (odpovědí). Pokud samotná aktuální hodnota není větší než dosavadní dočasný průběžný součet, pak se průběžný součet stane předchozím průběžným součtem plus aktuální hodnota, což je else část konstrukce if/else.
Poslední segment kódu ve smyčce for volí mezi libovolným předchozím maximálním součtem pro předchozí sekvenci (dílčí pole) a libovolným aktuálním maximálním součtem pro aktuální sekvenci. Proto je zvolena vyšší hodnota. Maximální součet dílčích polí může být více než jeden. Všimněte si, že průběžný součet by stoupal a klesal, protože pole je skenováno zleva doprava. Klesá, když se setká se zápornými hodnotami.
Konečný zvolený maximální součet dílčího pole je vrácen po cyklu for.
Obsah vhodné hlavní funkce C++ pro funkci Kadaneova 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 << síť4 << endl;
vektor < int > E = { 5 , 7 ,- 4 ,- 10 ,- 6 , 6 , 5 , 10 ,- 5 , patnáct , 4 ,- 8 ,- patnáct ,- 22 } ; // { 6 , 5 , 10 ,- 5 , patnáct , 4 } - > 35
int ret5 = maxSunArray ( A ) ;
cout << ret5 << endl;
vektor < int > F = { - 4 , 10 , patnáct , 9 ,- 5 ,- dvacet ,- 3 ,- 12 ,- 3 , 4 , 6 , 3 , dva , 8 , 3 ,- 5 ,- dva } ; // { 10 , patnáct , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << vpravo 6 << endl;
S tím bude výstup:
10
6
5
dvacet
35
3. 4
Každý řádek odpovědi zde odpovídá danému poli, v pořadí.
Závěr
Časová složitost pro Kadaneův algoritmus je O(n), kde n je počet prvků v daném poli. Tato časová složitost je nejrychlejší pro problém maximálního dílčího pole. Existují další algoritmy, které jsou pomalejší. Myšlenka Kadaneova algoritmu je provádět průběžný součet a přitom porovnávat maximální součty tak, jak se vyskytují, a pohybovat se v daném poli zleva doprava. Pokud je samotná aktuální hodnota větší než dosavadní průběžný součet, stane se tato jednotlivá hodnota novým průběžným součtem. V opačném případě je nový průběžný součet předchozí průběžný součet plus aktuální prvek, jak se očekává, když je dané pole skenováno.
Může existovat více než jeden maximální součet pro různá možná dílčí pole. Je zvolen nejvyšší maximální součet pro všechna možná dílčí pole.
Jaké jsou omezující indexy pro rozsah zvoleného maximálního součtu? – To je diskuse na jindy!
Chrys