Maksimalt sub-array-problem i C ++

Maksimum sub-array-problem er det samme som maksimal skiveproblem. Denne opplæringen diskuterer problemet med koding i C++. Spørsmålet er: Hva er den maksimale summen av enhver mulig sekvens av påfølgende tall i en matrise? Dette kan bety hele matrisen. Dette problemet og dets løsning på ethvert språk, blir referert til som det maksimale under-array-problemet. Arrayen kan ha mulige negative tall.

Løsningen må være effektiv. Det må ha den raskeste tidskompleksiteten. Per nå er den raskeste algoritmen for løsningen kjent i det vitenskapelige samfunnet som Kadanes algoritme. Denne artikkelen forklarer Kadanes algoritme med C++.

Dataeksempler

Tenk på følgende vektor (matrise):

vektor A = 5, -7, 3, 5, -2, 4, -1;

Skiven (sub -array) med maksimal sum er sekvensen, 3, 5, -2, 4, som gir en sum på 10. Ingen andre mulige sekvenser, selv hele matrisen, vil gi en sum opp til verdien av 10. Hele matrisen gir en sum på 7, som ikke er den maksimale summen.

Tenk på følgende vektor:

vektor B = -2, 1, -3, 4, -1, 2, 1, -5, 4;

Skiven (sub-array) med den maksimale summen er sekvensen, 4, −1, 2, 1 som gir en sum på 6. Merk at det kan være negative tall innenfor underordnede for maksimal sum.

Tenk på følgende vektor:

vektor C = 3, 2, -6, 4, 0;

Skiven (sub-array) med maksimal sum er sekvensen, 3, 2 som gir en sum på 5.

Tenk på følgende vektor:

vektor D = 3, 2, 6, -1, 4, 5, -1, 2;

Undergruppen 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 E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22;

Det er to undergarriser med maksimale summer, her. Den høyere summen er den som blir betraktet som løsning (svar) for det maksimale under-array-problemet. Undergartene er: 5, 7 med en sum på 12 og 6, 5, 10, -5, 15, 4 med en sum på 35. Selvfølgelig er skiven med summen av 35, svaret.

Tenk på følgende vektor:

vektor F = -4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2;

Det er to undergarriser med maksimale summer. Den høyere summen er den som blir betraktet som løsning for det maksimale under-array-problemet. Undergartene er: 10, 15, 9 med en sum på 34 og 4, 6, 3, 2, 8, 3 med en sum på 26. Selvfølgelig er skiven med summen av 34 svaret fordi problemet er å se etter underarrangen med den høyeste summen og ikke underarrayen med den høyere summen.

Utvikle Kadanes algoritme

Informasjonen i denne delen av opplæringen er ikke det opprinnelige verket fra Kadane. Det er forfatterens egen måte å undervise i Kadanes algoritme. En av de ovennevnte vektorene, med de løpende totalene, er i denne tabellen:

Å kjøre totalt for en indeks er summen av alle de tidligere verdiene, inkludert den for indeksen. Det er to sekvenser med maksimale summer her. De er 5, 7, som gir en sum på 12 og 6, 5, 10, -5, 15, 4, som gir en sum på 35. Sekvensen som gir en sum på 35 er det som er ønsket.

Legg merke til at det for løpende totaler er to topper som er verdiene, 12 og 27. Disse toppene tilsvarer de siste indeksene for de to sekvensene.

Så ideen om Kadanes algoritme er å gjøre det løpende totalen mens de sammenligner maksimale summer når 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 på 26. Sekvensen som gir summen av 34, er det som er ønsket.

Legg merke til at det for løpende totaler er to topper som er verdiene, 30 og 13. Disse toppene tilsvarer de siste indeksene for de to sekvensene.

Igjen er ideen om Kadanes algoritme å gjøre det løpende totalen mens de sammenligner maksimale summer når de blir møtt, og beveger seg fra venstre til høyre i den gitte matrisen.

Kode etter Kadanes algoritme i C++

Koden gitt i denne delen av artikkelen er ikke nødvendigvis det Kadane brukte. Imidlertid er det av hans algoritme. Programmet som mange andre C ++ -programmer, ville begynne med:

#inkludere
#inkludere

ved hjelp av navneområdet STD;

Det er inkludering av iostream -biblioteket, som er ansvarlig for input og output. Standard navneområde brukes.

Ideen om Kadanes algoritme er å ha den løpende totalen mens de sammenligner de maksimale summerene som de blir møtt, og beveger seg fra venstre til høyre i det gitte utvalget. Funksjonen for algoritmen er:

int maxsunarray (vektor & A)
int n = a.størrelse();
int maxsum = a [0];
int runtotal = a [0];
for (int i = 1; i < N; i++)
int tempruntotal = runtotal + a [i]; // kan være mindre enn en [i]
if (a [i]> tempruntotal)
runtotal = a [i]; // i tilfelle en [i] er større enn å løpe totalt
ellers
runtotal = tempruntotal;
if (runtotal> maxsum) // sammenligne alle maksimale summer
MaxSum = Runtotal;

Return Maxsum;

Størrelsen, n av den gitte matrisen (vektoren) bestemmes. Variabelen, Maxsum er en av de mulige maksimale beløpene. En matrise har minst en maksimal sum. Variabelen, runtotal representerer løpende totalt ved hver indeks. De er begge initialisert med den første verdien av matrisen. I denne algoritmen, hvis den neste verdien i matrisen er større enn den løpende totalt, vil den neste verdien bli den nye løpende totalen.

Det er en hovedhjelp. Skanning begynner fra 1 og ikke null på grunn av initialiseringen av variablene, maksimal og runtotal til en [0] som det første elementet i den gitte matrisen.

I For-loop bestemmer den første uttalelsen en midlertidig løpende total ved å legge den nåværende verdien til den akkumulerte summen av alle de tidligere verdiene.

Deretter er det en IF/ellers konstruksjon. Hvis den nåværende verdien alene er større enn den løpende totalt 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 maksimal verdi (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 gjeldende verdi, - dette annet delen av IF/ellers konstruksjon.

Det siste kodesegmentet i For-loop velger mellom en hvilken som helst tidligere maksimal sum for en tidligere sekvens (sub-array) og enhver nåværende maksimal sum for en nåværende sekvens. Den høyere verdien er derfor valgt. Det kan være mer enn en maksimal sum under array. Legg merke til at den løpende totalen vil stige og falle, ettersom matrisen skannes fra venstre mot høyre. Det faller når det oppfyller negative verdier.

Den endelige valgte maksimale summen av undergrepet blir returnert etter for-loop.

Innholdet for en passende C ++ hovedfunksjon, for kadanens algoritmefunksjon er:

vektor A = 5, -7, 3, 5, -2, 4, -1; // 3, 5, -2, 4 -> 10
int ret1 = maxSunArray (a);
cout << ret1 << endl;
vektor B = -2, 1, -3, 4, -1, 2, 1, -5, 4; // 4, −1, 2, 1 -> 6
int ret2 = maxSunArray (b);
cout << ret2 << endl;
vektor C = 3, 2, -6, 4, 0; // 3, 2 -> 5
int ret3 = maxSunArray (c);
cout << ret3 << endl;
vektor D = 3, 2, 6, -1, 4, 5, -1, 2; // 3, 2, 6, -1, 4, 5, -1, 2 -> 5
int ret4 = maxSunArray (d);
cout << ret4 << endl;
vektor E = 5, 7, -4, -10, -6, 6, 5, 10, -5, 15, 4, -8, -15, -22; // 6, 5, 10, -5, 15, 4 -> 35
int ret5 = maxSunArray (e);
cout << ret5 << endl;
vektor F = -4, 10, 15, 9, -5, -20, -3, -12, -3, 4, 6, 3, 2, 8, 3, -5, -2; // 10, 15, 9-> 34
int ret6 = maxSunArray (f);
cout << ret6 << endl;

Med det vil utgangen være:

10

6

5

20

35

34

Hvert linjesvar her, tilsvarer en gitt matrise, i orden.

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 under-array-problemet. Det er andre algoritmer som er tregere. Ideen om Kadanes algoritme er å gjøre det løpende totalen, samtidig som de sammenligner de maksimale summer. 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øps -totalen den forrige løps -summen 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 underarrays. Den høyeste maksimale summen, for alle mulige underarriser, er valgt.

Hva er de begrensende indeksene for området for den valgte maksimale summen? - Det er diskusjon for en annen gang!

Chrys