Maksimum under-array-problem er det samme som maksimalt udsnitsproblem. Denne tutorial diskuterer problemet med kodning i C++. Spørgsmålet er: hvad er den maksimale sum af enhver mulig sekvens af fortløbende tal inden for en matrix? Dette kan betyde hele rækken. Dette problem og dets løsning på ethvert sprog, kaldes det maksimale sub-array-problem. Arrayet kan have mulige negative tal.
Løsningen skal være effektiv. Det skal have den hurtigste tidskompleksitet. Lige nu er den hurtigste algoritme til løsningen kendt i det videnskabelige samfund som Kadane's Algorithm. Denne artikel forklarer Kadanes algoritme med C++.
Dataeksempler
Overvej følgende vektor (array):
vektor < int > A = { 5 , - 7 , 3 , 5 , - to , 4 , - 1 } ;
Udsnittet (sub-array) med den maksimale sum er sekvensen, {3, 5, -2, 4}, som giver en sum på 10. Ingen anden mulig sekvens, selv hele arrayet, vil give en sum på op til værdien 10. Hele arrayet giver en sum på 7, hvilket ikke er den maksimale sum.
Overvej følgende vektor:
vektor < int > B = { - to , 1 , - 3 , 4 , - 1 , to , 1 , - 5 , 4 } ;
Udsnittet (sub-array) med den maksimale sum er sekvensen, {4, −1, 2, 1}, som giver en sum på 6. Bemærk, at der kan være negative tal inden for sub-arrayet for maksimal sum.
Overvej følgende vektor:
vektor < int > C = { 3 , to , - 6 , 4 , 0 } ;
Udsnittet (under-array) med den maksimale sum er sekvensen, {3, 2}, som giver en sum på 5.
Overvej følgende vektor:
vektor < int > D = { 3 , to , 6 , - 1 , 4 , 5 , - 1 , to } ;
Underarrayet med den maksimale sum er sekvensen, {3, 2, 6, -1, 4, 5, -1, 2}, som giver en sum på 20. Det er hele arrayet.
Overvej følgende vektor:
vektor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , femten , 4 , - 8 , - femten , - 22 } ;
Der er to sub-arrays med maksimale summer her. Den højere sum er den, der betragtes som løsning (svar) for det maksimale sub-array-problem. Underarrayerne er: {5, 7} med summen 12 og {6, 5, 10, -5, 15, 4} med summen 35. Selvfølgelig er udsnittet med summen af 35 svaret.
Overvej følgende vektor:
vektor < int > F = { - 4 , 10 , femten , 9 , - 5 , - tyve , - 3 , - 12 , - 3 , 4 , 6 , 3 , to , 8 , 3 , - 5 , - to } ;
Der er to sub-arrays med maksimale summer. Den højere sum er den, der betragtes som løsning for det maksimale sub-array-problem. Underarrayerne er: {10, 15, 9} med summen 34 og {4, 6, 3, 2, 8, 3} med summen 26. Selvfølgelig er udsnittet med summen af 34 svaret, fordi problemet er at lede efter sub-arrayet med den højeste sum og ikke sub-arrayet med den højeste sum.
Udvikling af Kadanes algoritme
Oplysningerne i dette afsnit af selvstudiet er ikke det originale værk fra Kadane. Det er forfatterens egen måde at lære Kadanes algoritme på. En af ovenstående vektorer med dens løbende totaler er i denne tabel:
| Data | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | femten | 4 | -8 | -femten | -22 |
| Løb i alt | 5 | 12 | 8 | -to | -8 | -to | 3 | 13 | 8 | 23 | 27 | enogtyve | 16 | -6 |
| indeks | 0 | 1 | to | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elleve | 12 | 13 |
Løbende total for et indeks er summen af alle de tidligere værdier inklusive værdien for indekset. Der er to sekvenser med maksimale summer her. De er {5, 7}, som giver summen 12, og {6, 5, 10, -5, 15, 4}, som giver summen 35. Rækkefølgen, der giver summen 35, er det, der ønskes .
Bemærk, at for de løbende totaler er der to peaks, som er værdierne, 12 og 27. Disse peaks svarer til de sidste indekser af de to sekvenser.
Så ideen med Kadanes algoritme er at lave den løbende total, mens man sammenligner de maksimale summer, efterhånden som de stødes på, og bevæger sig fra venstre mod højre i det givne array.
En anden vektor ovenfra, med dens løbende totaler, er i denne tabel:
Der er to sekvenser med maksimale summer. De er {10, 15, 9}, hvilket giver en sum på 34; og {4, 6, 3, 2, 8, 3}, som giver en sum på 26. Den rækkefølge, der giver summen af 34, er det, der ønskes.
Bemærk, at for de løbende totaler er der to toppe, som er værdierne, 30 og 13. Disse toppe svarer til de sidste indekser af de to sekvenser.
Igen er ideen med Kadanes algoritme at lave den løbende total, mens man sammenligner de maksimale summer, efterhånden som de stødes på, bevæger sig fra venstre mod højre i det givne array.
Kode af Kadane's Algorithm i C++
Koden givet i dette afsnit af artiklen er ikke nødvendigvis, hvad Kadane brugte. Det er dog efter hans algoritme. Programmet vil ligesom mange andre C++-programmer begynde med:
#include#inkluder
bruger navneområde std;
Der er inklusion af iostream-biblioteket, som er ansvarlig for input og output. Standardnavnerummet bruges.
Ideen med Kadanes algoritme er at have den løbende total, mens man sammenligner de maksimale summer, efterhånden som de stødes på, bevæger sig fra venstre mod højre i det givne array. Funktionen for algoritmen er:
int maxSunArray ( vektor < int > & EN ) {int N = A.størrelse ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
til ( int jeg = 1 ; jeg < N; i++ ) {
int tempRunTotal = runTotal + A [ jeg ] ; // kunne være mindre end A [ jeg ]
hvis ( EN [ jeg ] > tempRunTotal )
runTotal = A [ jeg ] ; // i sag EN [ jeg ] er større end i alt
andet
runTotal = tempRunTotal;
hvis ( runTotal > maxBeløb ) // sammenligner alle de maksimale beløb
maxSum = runTotal;
}
Vend tilbage maxBeløb;
}
Størrelsen N af det givne array (vektor) bestemmes. Variablen maxSum er en af de mulige maksimumsummer. Et array har mindst én maksimal sum. Variablen runTotal repræsenterer den løbende total ved hvert indeks. De initialiseres begge med den første værdi af arrayet. I denne algoritme, hvis den næste værdi i arrayet er større end den løbende total, vil den næste værdi blive den nye løbende total.
Der er én hoved-for-loop. Scanning begynder fra 1 og ikke nul på grund af initialiseringen af variablerne, maxSum og runTotal til A[0], som er det første element i det givne array.
I for-løkken bestemmer den første sætning en midlertidig løbende total ved at lægge den aktuelle værdi til den akkumulerede sum af alle de tidligere værdier.
Dernæst er der en hvis/andet konstruktion. Hvis den aktuelle værdi alene er større end den løbende total indtil videre, bliver den enkelte værdi den løbende total. Dette er praktisk, især hvis alle værdierne i det givne array er negative. I dette tilfælde vil den højeste negative værdi alene blive den maksimale værdi (svaret). Hvis den aktuelle værdi alene ikke er større end den midlertidige løbende total indtil videre, bliver den løbende total den tidligere løbende total plus den aktuelle værdi, - dette er den anden del af if/else-konstruktionen.
Det sidste kodesegment i for-løkken vælger mellem en hvilken som helst tidligere maksimumsum for en tidligere sekvens (under-array) og enhver aktuel maksimumsum for en aktuel sekvens. Den højere værdi er derfor valgt. Der kan være mere end én maksimal sub-array sum. Bemærk, at den løbende total vil stige og falde, da arrayet scannes fra venstre mod højre. Det falder, når det møder negative værdier.
Den endelige valgte maksimale sub-array-sum returneres efter for-løkken.
Indholdet for en passende C++-hovedfunktion for Kadanes algoritmefunktion er:
vektor < int > A = { 5 , - 7 , 3 , 5 , - to , 4 , - 1 } ; // { 3 , 5 , - to , 4 } - > 10int ret1 = maxSunArray ( EN ) ;
cout << ret1 << endl;
vektor < int > B = { - to , 1 , - 3 , 4 , - 1 , to , 1 , - 5 , 4 } ; // { 4 , - 1 , to , 1 } - > 6
int ret2 = maxSunArray ( B ) ;
cout << ret2 << endl;
vektor < int > C = { 3 , to , - 6 , 4 , 0 } ; // { 3 , to } - > 5
int ret3 = maxSunArray ( C ) ;
cout << ret3 << endl;
vektor < int > D = { 3 , to , 6 , - 1 , 4 , 5 , - 1 , to } ; // { 3 , to , 6 , - 1 , 4 , 5 , - 1 , to } - > 5
int ret4 = maxSunArray ( D ) ;
cout << net4 << endl;
vektor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , femten , 4 , - 8 , - femten , - 22 } ; // { 6 , 5 , 10 , - 5 , femten , 4 } - > 35
int ret5 = maxSunArray ( OG ) ;
cout << ret5 << endl;
vektor < int > F = { - 4 , 10 , femten , 9 , - 5 , - tyve , - 3 , - 12 , - 3 , 4 , 6 , 3 , to , 8 , 3 , - 5 , - to } ; // { 10 , femten , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << ret6 << endl;
Med det bliver outputtet:
10
6
5
tyve
35
3. 4
Hvert linjesvar her svarer til en given matrix i rækkefølge.
Konklusion
Tidskompleksiteten for Kadanes algoritme er O(n), hvor n er antallet af elementer i det givne array. Denne tidskompleksitet er den hurtigste for det maksimale sub-array-problem. Der er andre algoritmer, der er langsommere. Ideen med Kadanes algoritme er at lave den løbende total, mens man sammenligner de maksimale summer, efterhånden som de stødes på, bevæger sig fra venstre mod højre i det givne array. Hvis den aktuelle værdi alene er større end den løbende total indtil videre, bliver den enkelte værdi den nye løbende total. Ellers er den nye løbende total den tidligere løbende total plus det nuværende element, som forventet, efterhånden som det givne array scannes.
Der kan være mere end én maksimal sum for forskellige mulige underarrays. Den højeste maksimale sum, for alle de mulige sub-arrays, vælges.
Hvad er de begrænsende indekser for rækkevidden af den valgte maksimale sum? – Det er diskussion til en anden gang!
Chrys