Maksimalt underarrangeproblem i Java
1. Oversigt
Det maksimale underarrayproblem er en opgave at finde serien af sammenhængende elementer med den maksimale sum i et givet array.
For eksempel i nedenstående array, det fremhævede underarray har den maksimale sum (6):
I denne vejledning ser vi på to løsninger til at finde det maksimale underarray i en matrix. En af dem vi designer med På) tid og rum kompleksitet.
2. Brute Force-algoritme
Brute force er en iterativ tilgang til at løse et problem. I de fleste tilfælde kræver løsningen et antal iterationer over en datastruktur. I de næste par afsnit anvender vi denne tilgang til at løse det maksimale underarrangeproblem.
2.1. Nærme sig
Generelt er den første løsning, der kommer til at tænke på, at beregne summen af alle mulige underarrangementer og returnere den med den maksimale sum.
Til at begynde med beregner vi summen af hvert underarray, der starter ved indeks 0. Og på lignende måde Vi finder alle underarrays startende ved hvert indeks fra 0 til n-1 hvor n er arrayets længde:
Så vi starter ved indeks 0 og tilføj hvert element til den løbende sum i iterationen. Det gør vi også holde styr på det maksimale beløb, der hidtil er set. Denne iteration vises på venstre side af billedet ovenfor.
På højre side af billedet kan vi se iteration, der starter ved indeks 3. I den sidste del af dette billede har vi underarrangementet med den maksimale sum mellem indekset 3 og 6.
Imidlertid, vores algoritme vil fortsætte med at finde alle underarrays, der starter ved indeks imellem 0 og n-1.
2.2. Implementering
Lad os nu se, hvordan vi kan implementere denne løsning i Java:
public int maxSubArray (int [] nums) {int n = nums.length; int maximumSubArraySum = Heltal.MIN_VALUE; int start = 0; int ende = 0; for (int left = 0; left <n; left ++) {int runningWindowSum = 0; for (int højre = venstre; højre maximumSubArraySum) {maximumSubArraySum = runningWindowSum; start = venstre; slut = højre; }}} logger.info ("Fundet maksimalt underarray mellem {} og {}", start, slut); return maximumSubArraySum; }Som forventet opdaterer vi maximumSubArraySum hvis den aktuelle sum er mere end den tidligere maksimale sum. Især så opdaterer vi også Start og ende for at finde ud af indeksplaceringerne for dette underarray.
2.3. Kompleksitet
Generelt gentager brute force-løsningen over arrayet mange gange for at få alle mulige løsninger. Dette betyder, at den tid, det tager af denne løsning, vokser kvadratisk med antallet af elementer i arrayet. Dette er muligvis ikke et problem for arrays af en lille størrelse. Men da størrelsen på arrayet vokser, er denne løsning ikke effektiv.
Ved at inspicere koden kan vi også se, at der er to indlejrede til sløjfer. Derfor kan vi konkludere, at tidskompleksiteten af denne algoritme er O (n2).
I de senere afsnit løser vi dette problem i På) kompleksitet ved hjælp af dynamisk programmering.
3. Dynamisk programmering
Dynamisk programmering løser et problem ved at opdele det i mindre delproblemer. Dette ligner meget opdelings-og-erobre algoritme til løsning af teknik. Den største forskel er dog, at dynamisk programmering kun løser et underproblem én gang.
Derefter gemmer resultatet af dette underproblem og genbruger senere dette resultat til at løse andre relaterede delproblemer. Denne proces kaldes memoization.
3.1. Kadanes algoritme
Kadanes algoritme er en populær løsning på det maksimale underarrayproblem, og denne løsning er baseret på dynamisk programmering.
Den vigtigste udfordring i at løse en dynamisk programmering problemet er at finde de optimale delproblemer.
3.2. Nærme sig
Lad os forstå dette problem på en anden måde:
På billedet ovenfor antager vi, at det maksimale underarrangement slutter ved den sidste indeksplacering. Derfor er den maksimale sum af underarray:
maximumSubArraySum = max_so_far + arr [n-1]max_so_far er den maksimale sum af et underarray, der ender ved indeks n-2. Dette vises også på billedet ovenfor.
Nu kan vi anvende denne antagelse på ethvert indeks i arrayet. For eksempel det maksimale subarraysum, der slutter ved n-2 kan beregnes som:
maximumSubArraySum [n-2] = max_so_far [n-3] + arr [n-2]Derfor kan vi konkludere, at:
maximumSubArraySum [i] = maximumSubArraySum [i-1] + arr [i]Nu, da hvert element i arrayet er et specielt underarray af størrelse 1, skal vi også kontrollere, om et element er større end selve den maksimale sum:
maximumSubArraySum [i] = Max (arr [i], maximumSubArraySum [i-1] + arr [i])Ved at se på disse ligninger kan vi se, at vi skal finde den maksimale subarraysum ved hvert indeks i matrixen. Således delte vi vores problem i n underproblemer. Vi kan finde den maksimale sum ved hvert indeks ved kun at gentage arrayet en gang:
Det fremhævede element viser det aktuelle element i iteration. Ved hvert indeks anvender vi den tidligere afledte ligning til at beregne en værdi for max_ending_here. Dette hjælper os med at identificere om vi skal inkludere det aktuelle element i underarrayet eller starte et nyt subarray, der starter ved dette indeks.
En anden variabel, max_so_far bruges til at gemme den maksimale subarraysum, der blev fundet under iterationen. Når vi gentager det sidste indeks, max_so_far gemmer summen af det maksimale underarray.
3.3. Implementering
Lad os igen se, hvordan vi nu kan implementere Kadane-algoritmen i Java ved at følge ovenstående tilgang:
public int maxSubArraySum (int [] arr) {int size = arr.length; int start = 0; int ende = 0; int maxSoFar = 0, maxEndingHere = 0; for (int i = 0; i maxEnding Here + arr [i]) {start = i; maxEnding Here = arr [i]; } ellers maxEndingHere = maxEndingHere + arr [i]; hvis (maxSoFar <maxEndingHere) {maxSoFar = maxEndingHere; slutning = i; }} logger.info ("Fundet maksimalt underarray mellem {} og {}", start, slut); returnere maxSoFar; }Her opdaterede vi Start og ende for at finde de maksimale underarrayindekser.
3.4. Kompleksitet
Da vi kun har brug for at gentage arrayet en gang, er tidskompleksiteten af denne algoritme På).
Så som vi kan se, vokser tiden med denne løsning lineært med antallet af elementer i arrayet. Derfor er den mere effektiv end den brute force-tilgang, vi diskuterede i det sidste afsnit.
4. Konklusion
I denne hurtige vejledning har vi beskrevet to måder at løse det maksimale underarrayproblem på.
Først undersøgte vi en brutal styrke tilgang og så, at denne iterative løsning resulterede i kvadratisk tid. Senere diskuterede vi derefter Kadane-algoritmen og brugte dynamisk programmering til at løse problemet i lineær tid.
Som altid er artiklens fulde kildekode tilgængelig på GitHub.
