Maximum Sub-Array Probleem is hetzelfde als Maximum Slice Probleem. Deze tutorial bespreekt het probleem met codering in C++. De vraag is: wat is de maximale som van elke mogelijke reeks opeenvolgende getallen binnen een array? Dit kan de hele array betekenen. Dit probleem en de oplossing ervan in elke taal wordt het Maximum Sub-Array Probleem genoemd. De array kan mogelijke negatieve getallen hebben.
De oplossing moet efficiënt zijn. Het moet de snelste tijdcomplexiteit hebben. Vanaf nu staat het snelste algoritme voor de oplossing in de wetenschappelijke gemeenschap bekend als Kadane's Algorithm. In dit artikel wordt het algoritme van Kadane met C++ uitgelegd.
Gegevensvoorbeelden
Beschouw de volgende vector (array):
vector < int > A = { 5 , - 7 , 3 , 5 , - twee , 4 , - 1 } ;
Het segment (sub-array) met de maximale som is de reeks, {3, 5, -2, 4}, die een som van 10 geeft. Geen enkele andere mogelijke reeks, zelfs de hele reeks, geeft een som van maximaal de waarde van 10. De hele array geeft een som van 7, wat niet de maximale som is.
Beschouw de volgende vector:
vector < int > B = { - twee , 1 , - 3 , 4 , - 1 , twee , 1 , - 5 , 4 } ;
De plak (sub-array) met de maximale som is de reeks, {4, −1, 2, 1} die een som van 6 geeft. Merk op dat er negatieve getallen binnen de sub-array kunnen zijn voor de maximale som.
Beschouw de volgende vector:
vector < int > C = { 3 , twee , - 6 , 4 , 0 } ;
De plak (sub-array) met de maximale som is de reeks, {3, 2} die een som van 5 geeft.
Beschouw de volgende vector:
vector < int > D = { 3 , twee , 6 , - 1 , 4 , 5 , - 1 , twee } ;
De sub-array met de maximale som is de rij, {3, 2, 6, -1, 4, 5, -1, 2} die een som van 20 geeft. Het is de hele array.
Beschouw de volgende vector:
vector < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , vijftien , 4 , - 8 , - vijftien , - 22 } ;
Er zijn hier twee sub-arrays met maximale bedragen. De hogere som is degene die wordt beschouwd als oplossing (antwoord) voor het maximale subarray-probleem. De subarrays zijn: {5, 7} met een som van 12, en {6, 5, 10, -5, 15, 4} met een som van 35. Natuurlijk is het segment met de som van 35 het antwoord.
Beschouw de volgende vector:
vector < int > F = { - 4 , 10 , vijftien , 9 , - 5 , - twintig , - 3 , - 12 , - 3 , 4 , 6 , 3 , twee , 8 , 3 , - 5 , - twee } ;
Er zijn twee sub-arrays met maximale bedragen. De hogere som is degene die wordt beschouwd als oplossing voor het maximale subarray-probleem. De subarrays zijn: {10, 15, 9} met een som van 34, en {4, 6, 3, 2, 8, 3} met een som van 26. Natuurlijk is het segment met de som van 34 het antwoord omdat het probleem is om te zoeken naar de subarray met de hoogste som en niet naar de subarray met de hogere som.
Ontwikkeling van het algoritme van Kadane
De informatie in dit gedeelte van de tutorial is niet het originele werk van Kadane. Het is de eigen manier van de auteur om het algoritme van Kadane te leren. Een van de bovenstaande vectoren, met zijn lopende totalen, staat in deze tabel:
| Gegevens | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | vijftien | 4 | -8 | -vijftien | -22 |
| Lopend totaal | 5 | 12 | 8 | -twee | -8 | -twee | 3 | 13 | 8 | 23 | 27 | eenentwintig | 16 | -6 |
| inhoudsopgave | 0 | 1 | twee | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elf | 12 | 13 |
Lopend totaal voor een index is de som van alle voorgaande waarden, inclusief die voor de index. Er zijn hier twee reeksen met maximale sommen. Ze zijn {5, 7}, wat een som van 12 geeft, en {6, 5, 10, -5, 15, 4}, wat een som van 35 geeft. De reeks die een som van 35 geeft, is wat gewenst is .
Merk op dat er voor de lopende totalen twee pieken zijn, de waarden 12 en 27. Deze pieken komen overeen met de laatste indexen van de twee reeksen.
Het idee van Kadane's algoritme is dus om het lopende totaal te doen terwijl de maximale sommen worden vergeleken wanneer ze worden aangetroffen, van links naar rechts in de gegeven array.
Een andere vector van boven, met zijn lopende totalen, staat in deze tabel:
Er zijn twee reeksen met maximale sommen. Ze zijn {10, 15, 9}, wat een som van 34 geeft; en {4, 6, 3, 2, 8, 3} die een som van 26 geeft. De rij die de som van 34 geeft, is wat gewenst is.
Merk op dat er voor de lopende totalen twee pieken zijn die de waarden 30 en 13 zijn. Deze pieken komen overeen met de laatste indexen van de twee reeksen.
Nogmaals, het idee van Kadane's algoritme is om het lopende totaal te doen terwijl de maximale sommen worden vergeleken wanneer ze worden aangetroffen, van links naar rechts in de gegeven array.
Code door Kadane's algoritme in C++
De code die in dit gedeelte van het artikel wordt gegeven, is niet noodzakelijk de code die Kadane heeft gebruikt. Het is echter door zijn algoritme. Het programma zou, net als veel andere C++-programma's, beginnen met:
#include#include
namespace std; gebruiken;
Er is een opname van de iostream-bibliotheek, die verantwoordelijk is voor invoer en uitvoer. De standaard naamruimte wordt gebruikt.
Het idee van Kadane's algoritme is om het lopende totaal te hebben terwijl de maximale sommen worden vergeleken wanneer ze worden aangetroffen, van links naar rechts in de gegeven array. De functie voor het algoritme is:
int maxSunArray ( vector < int > & EEN ) {int N = A. maat ( ) ;
int maxSum = A [ 0 ] ;
int runTotaal = A [ 0 ] ;
voor ( int i = 1 ; i < N; ik++ ) {
int tempRunTotal = runTotal + A [ i ] ; // kan kleiner zijn dan A [ i ]
als ( EEN [ i ] > tempRunTotal )
runTotaal = A [ i ] ; // in geval EEN [ i ] is groter dan het lopende totaal
anders
runTotal = tempRunTotal;
als ( runTotaal > maxbedrag ) // alle maximale bedragen vergelijken
maxSum = runTotaal;
}
opbrengst maxbedrag;
}
De grootte, N van de gegeven array (vector) wordt bepaald. De variabele maxSum is een van de mogelijke maximale sommen. Een array heeft ten minste één maximale som. De variabele runTotal vertegenwoordigt het lopende totaal bij elke index. Ze worden beide geïnitialiseerd met de eerste waarde van de array. Als in dit algoritme de volgende waarde in de array groter is dan het lopende totaal, wordt die volgende waarde het nieuwe lopende totaal.
Er is één grote for-loop. Het scannen begint bij 1 en niet bij nul vanwege de initialisatie van de variabelen maxSum en runTotal naar A[0], het eerste element van de gegeven array.
In de for-lus bepaalt de eerste instructie een tijdelijk lopend totaal door de huidige waarde op te tellen bij de geaccumuleerde som van alle voorgaande waarden.
Vervolgens is er een if/els-constructie. Als alleen de huidige waarde groter is dan het lopende totaal tot nu toe, wordt die ene waarde het lopende totaal. Dit is vooral handig als alle waarden in de gegeven array negatief zijn. In dit geval wordt alleen de hoogste negatieve waarde de maximale waarde (het antwoord). Als de huidige waarde alleen niet groter is dan het tijdelijke lopende totaal tot nu toe, dan wordt het lopende totaal het vorige lopende totaal plus de huidige waarde, dit is het else-deel van de if/else constructie.
Het laatste codesegment in de for-lus kiest tussen een eerdere maximale som voor een vorige reeks (sub-array) en een huidige maximale som voor een huidige reeks. Daarom wordt gekozen voor de hogere waarde. Er kan meer dan één maximale subarraysom zijn. Merk op dat het lopende totaal zou stijgen en dalen, aangezien de array van links naar rechts wordt gescand. Het valt als het voldoet aan negatieve waarden.
De uiteindelijk gekozen maximale subarraysom wordt geretourneerd na de for-lus.
De inhoud voor een geschikte C++-hoofdfunctie voor de algoritmefunctie van Kadane is:
vector < int > A = { 5 , - 7 , 3 , 5 , - twee , 4 , - 1 } ; // { 3 , 5 , - twee , 4 } - > 10int ret1 = maxSunArray ( EEN ) ;
cout << ret1 << endl;
vector < int > B = { - twee , 1 , - 3 , 4 , - 1 , twee , 1 , - 5 , 4 } ; // { 4 , 1 , twee , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << endl;
vector < int > C = { 3 , twee , - 6 , 4 , 0 } ; // { 3 , twee } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << endl;
vector < int > D = { 3 , twee , 6 , - 1 , 4 , 5 , - 1 , twee } ; // { 3 , twee , 6 , - 1 , 4 , 5 , - 1 , twee } - > 5
int ret4 = maxSunArray ( D ) ;
cout << net4 << endl;
vector < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , vijftien , 4 , - 8 , - vijftien , - 22 } ; // { 6 , 5 , 10 , - 5 , vijftien , 4 } - > 35
int ret5 = maxSunArray ( EN ) ;
cout << ret5 << endl;
vector < int > F = { - 4 , 10 , vijftien , 9 , - 5 , - twintig , - 3 , - 12 , - 3 , 4 , 6 , 3 , twee , 8 , 3 , - 5 , - twee } ; // { 10 , vijftien , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << rechts 6 << endl;
Daarmee wordt de output:
10
6
5
twintig
35
3. 4
Elk regelantwoord hier komt in volgorde overeen met een gegeven array.
Conclusie
De tijdcomplexiteit voor het algoritme van Kadane is O(n), waarbij n het aantal elementen in de gegeven array is. Deze keer is de complexiteit het snelst voor het maximale subarray-probleem. Er zijn andere algoritmen die langzamer zijn. Het idee van Kadane's algoritme is om het lopende totaal te doen, terwijl de maximale sommen worden vergeleken wanneer ze worden aangetroffen, van links naar rechts in de gegeven array. Als alleen de huidige waarde groter is dan het lopende totaal tot nu toe, wordt die enkele waarde het nieuwe lopende totaal. Anders is het nieuwe lopende totaal het vorige lopende totaal plus het huidige element, zoals verwacht, terwijl de gegeven array wordt gescand.
Er kan meer dan één maximale som zijn, voor verschillende mogelijke subarrays. De hoogste maximale som, voor alle mogelijke sub-arrays, wordt gekozen.
Wat zijn de beperkende indexen voor het bereik van de gekozen maximale som? – Dat is een discussie voor een andere keer!
Chrys