Maksimum undergruppeproblem er det samme som maksimalt stykkeproblem. Denne opplæringen diskuterer problemet med koding i C++. Spørsmålet er: hva er den maksimale summen av en mulig rekkefølge av påfølgende tall i en matrise? Dette kan bety hele matrisen. Dette problemet og dets løsning på et hvilket som helst språk, blir referert til som Maximum Sub-Array Problem. Matrisen kan ha mulige negative tall.
Løsningen må være effektiv. Den må ha den raskeste tidskompleksiteten. Per nå er den raskeste algoritmen for løsningen kjent i det vitenskapelige miljøet som Kadane's Algorithm. Denne artikkelen forklarer Kadanes algoritme med C++.
Dataeksempler
Tenk på følgende vektor (array):
vektor < int > A = { 5 , - 7 , 3 , 5 , - to , 4 , - 1 } ;
Skiven (undermatrisen) med maksimal sum er sekvensen, {3, 5, -2, 4}, som gir summen 10. Ingen annen mulig sekvens, selv hele matrisen, vil gi en sum på opptil verdien av 10. Hele matrisen gir en sum på 7, som ikke er den maksimale summen.
Tenk på følgende vektor:
vektor < int > B = { - to , 1 , - 3 , 4 , - 1 , to , 1 , - 5 , 4 } ;
Skiven (undermatrisen) med maksimal sum er sekvensen, {4, −1, 2, 1} som gir summen 6. Merk at det kan være negative tall innenfor undermatrisen for maksimal sum.
Tenk på følgende vektor:
vektor < int > C = { 3 , to , - 6 , 4 , 0 } ;
Skiven (undermatrisen) med maksimal sum er sekvensen, {3, 2} som gir summen 5.
Tenk på følgende vektor:
vektor < int > D = { 3 , to , 6 , - 1 , 4 , 5 , - 1 , to } ;
Undermatrisen med maksimal sum er sekvensen, {3, 2, 6, -1, 4, 5, -1, 2} som gir en sum på 20. Det er hele matrisen.
Tenk på følgende vektor:
vektor < int > E = { 5 , 7 , - 4 , - 10 , - 6 , 6 , 5 , 10 , - 5 , femten , 4 , - 8 , - femten , - 22 } ;
Det er to undermatriser med maksimale summer her. Den høyere summen er den som anses som løsning (svar) for det maksimale sub-array-problemet. Undermatrisene er: {5, 7} med summen 12, og {6, 5, 10, -5, 15, 4} med summen 35. Selvfølgelig er skiven med summen 35 svaret.
Tenk på følgende vektor:
vektor < int > F = { - 4 , 10 , femten , 9 , - 5 , - tjue , - 3 , - 12 , - 3 , 4 , 6 , 3 , to , 8 , 3 , - 5 , - to } ;
Det er to undermatriser med maksimale summer. Den høyere summen er den som anses som løsning for det maksimale sub-array-problemet. Undermatrisene er: {10, 15, 9} med summen 34, og {4, 6, 3, 2, 8, 3} med summen 26. Selvfølgelig er skiven med summen 34 svaret fordi problemet er å se etter sub-arrayen med den høyeste summen og ikke sub-arrayen med den høyeste summen.
Utvikler Kadanes algoritme
Informasjonen i denne delen av opplæringen er ikke det originale verket fra Kadane. Det er forfatterens egen måte å lære Kadanes algoritme på. En av vektorene ovenfor, med sine løpende totaler, er i denne tabellen:
| Data | 5 | 7 | -4 | -10 | -6 | 6 | 5 | 10 | -5 | femten | 4 | -8 | -femten | -22 |
| Løpende totalt | 5 | 12 | 8 | -to | -8 | -to | 3 | 1. 3 | 8 | 23 | 27 | tjueen | 16 | -6 |
| indeks | 0 | 1 | to | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elleve | 12 | 1. 3 |
Løpende total for en indeks er summen av alle tidligere verdier inkludert verdien for indeksen. Det er to sekvenser med maksimale summer her. De er {5, 7}, som gir summen 12, og {6, 5, 10, -5, 15, 4}, som gir summen 35. Rekkefølgen som gir summen 35 er det som ønskes .
Legg merke til at for de løpende totalene er det to topper som er verdiene, 12 og 27. Disse toppene tilsvarer de siste indeksene av de to sekvensene.
Så, ideen med Kadanes algoritme er å gjøre den løpende totalen mens du sammenligner de maksimale summene etter hvert som de blir møtt, og beveger seg fra venstre til høyre i den gitte matrisen.
En annen vektor ovenfra, med sine løpende totaler, er i denne tabellen:
Det er to sekvenser med maksimale summer. De er {10, 15, 9}, som gir en sum på 34; og {4, 6, 3, 2, 8, 3} som gir en sum av 26. Rekkefølgen som gir summen av 34, er det som er ønsket.
Legg merke til at for de løpende totalene er det to topper som er verdiene, 30 og 13. Disse toppene tilsvarer de siste indeksene til de to sekvensene.
Igjen, ideen til Kadanes algoritme er å gjøre den løpende summen mens man sammenligner de maksimale summene etter hvert som de blir møtt, og beveger seg fra venstre til høyre i den gitte matrisen.
Kode av Kadane's Algorithm i C++
Koden gitt i denne delen av artikkelen er ikke nødvendigvis det Kadane brukte. Det er imidlertid etter hans algoritme. Programmet vil, som mange andre C++-programmer, begynne med:
#include#inkluder
bruker navneområde std;
Det er inkludering av iostream-biblioteket, som er ansvarlig for input og output. Standard navneområde brukes.
Ideen til Kadanes algoritme er å ha den løpende totalen mens man sammenligner de maksimale summene etter hvert som de støtes på, og beveger seg fra venstre til høyre i den gitte matrisen. Funksjonen for algoritmen er:
int maxSunArray ( vektor < int > & EN ) {int N = A.str ( ) ;
int maxSum = A [ 0 ] ;
int runTotal = A [ 0 ] ;
til ( int Jeg = 1 ; Jeg < N; i++ ) {
int tempRunTotal = runTotal + A [ Jeg ] ; // kan være mindre enn A [ Jeg ]
hvis ( EN [ Jeg ] > tempRunTotal )
runTotal = A [ Jeg ] ; // i sak EN [ Jeg ] er større enn totalsummen
ellers
runTotal = tempRunTotal;
hvis ( runTotal > maxAmount ) // sammenligne alle maksimumsbeløpene
maxSum = runTotal;
}
komme tilbake maxAmount;
}
Størrelsen, N til den gitte matrisen (vektor) bestemmes. Variabelen, maxSum er en av de mulige maksimumssummene. En matrise har minst én maksimal sum. Variabelen runTotal representerer den løpende totalen ved hver indeks. De initialiseres begge med den første verdien av matrisen. I denne algoritmen, hvis den neste verdien i matrisen er større enn den løpende totalen, vil den neste verdien bli den nye løpende totalen.
Det er én hovedfor-løkke. Skanning begynner fra 1 og ikke null på grunn av initialiseringen av variablene, maxSum og runTotal til A[0] som er det første elementet i den gitte matrisen.
I for-løkken bestemmer den første setningen en midlertidig løpende total ved å legge til gjeldende verdi til den akkumulerte summen av alle de tidligere verdiene.
Deretter er det en hvis/anne-konstruksjon. Hvis gjeldende verdi alene er større enn den løpende totalen så langt, blir den enkeltverdien den løpende totalen. Dette er nyttig spesielt hvis alle verdiene i den gitte matrisen er negative. I dette tilfellet vil den høyeste negative verdien alene bli maksimalverdien (svaret). Hvis den nåværende verdien alene ikke er større enn den midlertidige løpende totalen så langt, blir den løpende totalen den forrige løpende totalen pluss den nåværende verdien, - dette er den andre delen av if/else-konstruksjonen.
Det siste kodesegmentet i for-løkken velger mellom en hvilken som helst tidligere maksimalsum for en tidligere sekvens (undermatrise) og en hvilken som helst gjeldende maksimumsum for en gjeldende sekvens. Den høyere verdien er derfor valgt. Det kan være mer enn én maksimal sub-array sum. Legg merke til at den løpende summen vil stige og falle, ettersom matrisen skannes fra venstre til høyre. Den faller når den møter negative verdier.
Den endelige valgte maksimale sub-array-summen returneres etter for-løkken.
Innholdet for en passende C++ hovedfunksjon, for Kadanes algoritmefunksjon 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 << nett4 << 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 , - tjue , - 3 , - 12 , - 3 , 4 , 6 , 3 , to , 8 , 3 , - 5 , - to } ; // { 10 , femten , 9 } - > 3. 4
int ret6 = maxSunArray ( F ) ;
cout << høyre 6 << endl;
Med det vil utgangen være:
10
6
5
tjue
35
3. 4
Hvert linjesvar her tilsvarer en gitt matrise, i rekkefølge.
Konklusjon
Tidskompleksiteten for Kadanes algoritme er O(n), der n er antall elementer i den gitte matrisen. Denne tidskompleksiteten er den raskeste for det maksimale sub-array-problemet. Det er andre algoritmer som er tregere. Ideen til Kadanes algoritme er å gjøre den løpende summen, mens man sammenligner de maksimale summene etter hvert som de støtes på, og beveger seg fra venstre til høyre i den gitte matrisen. Hvis den nåværende verdien alene er større enn den løpende totalen så langt, blir den enkeltverdien den nye løpende totalen. Ellers er den nye løpende totalen den forrige løpende totalen pluss det nåværende elementet, som forventet, ettersom den gitte matrisen skannes.
Det kan være mer enn én maksimal sum, for forskjellige mulige sub-arrays. Den høyeste maksimale summen, for alle mulige sub-arrays, velges.
Hva er de begrensende indeksene for rekkevidden til den valgte maksimale summen? – Det er diskusjon for en annen gang!
Chrys