streamalism.org

1. Oversikt

Det maksimale underarrangeproblemet er en oppgave å finne serien av sammenhengende elementer med maksimumssummen i en gitt matrise.

For eksempel i matrisen nedenfor, den uthevede undergruppen har maksimal sum (6):

I denne opplæringen tar vi en titt på to løsninger for å finne det maksimale underarrangementet i en matrise. En av dem vi skal designe med På) tid og rom kompleksitet.

2. Brute Force-algoritme

Brute force er en iterativ tilnærming for å løse et problem. I de fleste tilfeller krever løsningen en rekke iterasjoner over en datastruktur. I de neste avsnittene bruker vi denne tilnærmingen for å løse det maksimale underarrangeproblemet.

2.1. Nærme seg

Generelt sett er den første løsningen som kommer til å tenke på å beregne summen av alle mulige undergrupper og returnere den med maksimumssummen.

Til å begynne med beregner vi summen av hver undergruppe som starter ved indeks 0. Og på samme måte, Vi finner alle underarrangementer som starter ved hver indeks fra 0 til n-1 hvor n er lengden på matrisen:

Så vi starter på indeksen 0 og legg til hvert element i den løpende summen i iterasjonen. Vi vil også holde oversikt over den maksimale summen så langt. Denne iterasjonen vises på venstre side av bildet ovenfor.

På høyre side av bildet kan vi se iterasjonen som starter ved indeks 3. I den siste delen av dette bildet har vi underordnet med den maksimale summen mellom indeksen 3 og 6.

Derimot, algoritmen vår vil fortsette å finne alle underordninger som starter på indekser mellom 0 og n-1.

2.2. Gjennomføring

La oss nå se hvordan vi kan implementere denne løsningen i Java:

public int maxSubArray (int [] nums) {int n = nums.length; int maximumSubArraySum = Heltall.MIN_VALUE; int start = 0; int end = 0; for (int left = 0; left <n; left ++) {int runningWindowSum = 0; for (int høyre = venstre; høyre maximumSubArraySum) {maximumSubArraySum = runningWindowSum; start = venstre; slutt = høyre; }}} logger.info ("Fant maksimalt underarray mellom {} og {}", start, slutt); return maximumSubArraySum; }

Som forventet oppdaterer vi maximumSubArraySum hvis den nåværende summen er mer enn den forrige maksimumssummen. Spesielt vi oppdaterer da også start og slutt for å finne ut indeksplasseringene til denne undergruppen.

2.3. Kompleksitet

Generelt sett går brute force-løsningen over matrisen mange ganger for å få alle mulige løsninger. Dette betyr at tiden det tar med denne løsningen vokser kvadratisk med antall elementer i matrisen. Dette kan ikke være et problem for matriser av liten størrelse. Men ettersom størrelsen på matrisen vokser, er denne løsningen ikke effektiv.

Ved å inspisere koden kan vi også se at det er to nestede til løkker. Derfor kan vi konkludere med at tidskompleksiteten til denne algoritmen er O (n2).

I de senere avsnittene løser vi dette problemet i På) kompleksitet ved hjelp av dynamisk programmering.

3. Dynamisk programmering

Dynamisk programmering løser et problem ved å dele det inn i mindre delproblemer. Dette ligner veldig på teknikken for algoritme for deling og erobring. Den største forskjellen er imidlertid at dynamisk programmering bare løser et underproblem en gang.

Den lagrer deretter resultatet av dette delproblemet og gjenbruker senere dette resultatet til å løse andre relaterte delproblemer. Denne prosessen er kjent som memoization.

3.1. Kadanes algoritme

Kadanes algoritme er en populær løsning på det maksimale underarrangeproblemet, og denne løsningen er basert på dynamisk programmering.

Den viktigste utfordringen i å løse en dynamisk programmering problemet er å finne de optimale delproblemene.

3.2. Nærme seg

La oss forstå dette problemet på en annen måte:

I bildet over antar vi at den maksimale undergruppen slutter på den siste indeksplasseringen. Derfor vil den maksimale summen av undergruppe være:

maximumSubArraySum = max_so_far + arr [n-1]

max_so_far er den maksimale summen av en undergruppe som ender ved indeks n-2. Dette vises også på bildet over.

Nå kan vi bruke denne antagelsen til hvilken som helst indeks i matrisen. For eksempel den maksimale subarray-summen som ender på n-2 kan beregnes som:

maximumSubArraySum [n-2] = max_so_far [n-3] + arr [n-2]

Derfor kan vi konkludere med at:

maximumSubArraySum [i] = maximumSubArraySum [i-1] + arr [i]

Nå, siden hvert element i matrisen er en spesiell undergruppe av størrelse en, må vi også sjekke om et element er større enn selve maksimumssummen:

maximumSubArraySum [i] = Maks (arr [i], maximumSubArraySum [i-1] + arr [i])

Ved å se på disse ligningene kan vi se at vi trenger å finne den maksimale subarray-summen ved hver indeks i matrisen. Dermed delte vi problemet vårt inn i n delproblemer. Vi kan finne den maksimale summen ved hver indeks ved å gjenta matrisen bare en gang:

Det uthevede elementet viser gjeldende element i iterasjonen. Ved hver indeks bruker vi ligningen avledet tidligere for å beregne en verdi for max_ending_here. Dette hjelper oss med å identifisere om vi skal inkludere det nåværende elementet i underarrayet eller starte et nytt subarray som starter ved denne indeksen.

En annen variabel, max_so_far brukes til å lagre den maksimale subarray-sum som ble funnet under iterasjonen. Når vi gjentar oss over den siste indeksen, max_so_far lagrer summen av det maksimale underarrangementet.

3.3. Gjennomføring

Igjen, la oss se hvordan vi nå kan implementere Kadane-algoritmen i Java, ved å følge fremgangsmåten ovenfor:

public int maxSubArraySum (int [] arr) {int size = arr.length; int start = 0; int end = 0; int maxSoFar = 0, maxEndingHere = 0; for (int i = 0; i maxEndingHere + arr [i]) {start = i; maxEndingHere = arr [i]; } ellers maxEndingHere = maxEndingHere + arr [i]; hvis (maxSoFar <maxEndingHere) {maxSoFar = maxEndingHere; slutt = i; }} logger.info ("Fant maksimalt underarray mellom {} og {}", start, slutt); retur maxSoFar; }

Her oppdaterte vi start og slutt for å finne maksimale underordnede indekser.

3.4. Kompleksitet

Siden vi bare trenger å gjenta matrisen en gang, er tidskompleksiteten til denne algoritmen På).

Så som vi kan se, vokser tiden med denne løsningen lineært med antall elementer i matrisen. Følgelig er det mer effektivt enn brute force-tilnærmingen vi diskuterte i forrige avsnitt.

4. Konklusjon

I denne raske opplæringen har vi beskrevet to måter å løse det maksimale underarrangeproblemet på.

Først utforsket vi en brute force-tilnærming og så at denne iterative løsningen resulterte i kvadratisk tid. Senere diskuterte vi Kadane-algoritmen og brukte dynamisk programmering for å løse problemet i lineær tid.

Som alltid er hele kildekoden til artikkelen tilgjengelig på GitHub.