Hvis du er her, er chancerne for, at du forsøgte at løse det “maksimale Subarray-Problem” og stødte på Kadanes algoritme, men kunne ikke finde ud af, hvordan sådan noget fungerer. Eller måske var du træt af at bruge Kadanes algoritme som en “black-bo.”. Eller måske ville du forstå det dynamiske programmeringsaspekt af det. Eller måske vil du bare lære om et nyt koncept, der kan gøre dig bedre til programmering. Uanset årsagen er du kommet til det rigtige sted.,
for bedre at forstå Kadanes algoritme ville vi først gennemgå en kort introduktion af dynamisk programmering. Derefter ville vi se på et ganske populært programmeringsproblem, det maksimale Subarray-Problem. Vi ville se, hvordan dette problem kan løses ved hjælp af en brute force-tilgang, og så ville vi forsøge at forbedre vores tilgang og komme med en bedre algoritme, aka, Kadanes algoritme.
så lad os komme ind i det.,
Dynamisk Programmering
Dynamisk Programmering er en metode til at løse et komplekst problem, ved at bryde det ned i en samling af enklere subproblems, løse hver enkelt af disse subproblems bare én gang, og gemme deres løsninger ved hjælp af en memory baseret datastruktur (array, kort, osv.). Så næste gang det samme underproblem opstår, i stedet for at beregne sin løsning igen, ser man simpelthen op på den tidligere beregnede løsning og sparer derved beregningstid.
de, der ikke kan huske fortiden, er dømt til at gentage den., — Dynamisk Programmering
Her er en genial forklaring på begrebet Dynamisk Programmering på Quora — Jonathan Paulson ‘ s svar på, Hvordan skal jeg forklare, dynamisk programmering til en 4-årig?
selvom der er mere til dynamisk programmering, vil vi gå videre for at forstå det maksimale Subarray-Problem.
den Maksimale Subarray Problem
Den maksimale subarray problem er opgaven at finde den størst mulige sum af en sammenhængende subarray, inden for en given én-dimensionelle array-En af numre.,
For eksempel, for det array, der er givet ovenfor, sammenhængende subarray med den største sum er , med sum 6. Vi ville bruge dette array som vores eksempel for resten af denne artikel. Vi antager også, at dette array er nulindekseret, dvs. -2 ville blive kaldt som ‘ 0th ‘ – elementet i arrayet og så videre. Også, a ville repræsentere værdien ved indeks i.,
nu vil vi se på en meget indlysende løsning på det givne problem.
Brute Force Tilgang
En meget indlysende, men ikke så god løsning er at beregne summen af alle mulige subarray og det maksimale af dem ville være løsningen. Vi kan starte fra indeks 0 og beregne summen af alle mulige subarray startende med element a, som vist i figuren nedenfor. Derefter beregner vi summen af alle mulige subarray, der starter med A, A og så videre op til A, hvor n angiver størrelsen på arrayet (n = 9 i vores tilfælde)., Bemærk, at hvert enkelt element er en subarray selv.
Vi vil kalde den maksimale sum af subarrays starter med Et element a den local_maximum på indeks jeg. Således efter at gå gennem alle de indekser, ville vi stå tilbage med local_maximum for alle indeks. Endelig kan vi finde det maksimale af disse local_ma andimums, og vi ville få den endelige løsning, dvs., den maksimale sum muligt. Vi vil kalde dette global_ma .imum.
men du kan bemærke, at dette ikke er en særlig god metode, fordi antallet af mulige subarrays stiger hurtigt, hvilket øger beregningskompleksiteten, når størrelsen på arrayet øges. Eller for at være mere præcis, hvis størrelsen af arrayet er n, så er tidskompleksiteten af denne løsning O(n2), hvilket ikke er meget godt.
hvordan kan vi forbedre dette? Er der nogen måde at bruge begrebet dynamisk programmering på? Lad os finde ud af det.,
Kadanes algoritme
i dette afsnit ville vi bruge den brute force-tilgang, der er diskuteret ovenfor igen, men denne gang ville vi starte baglæns. Hvordan ville det hjælpe? Lad os se.
Vi ville starte fra det sidste element og beregne summen af alle mulige subarray, der slutter med elementet A, som vist i figuren nedenfor. Derefter, vi beregner summen af alle mulige subarray, der slutter med A, A og så videre op til A.,
lad os Nu fokusere på den subarrays slutter med Et element a (=-1) og (=2) som vist i figuren nedenfor.,
Fra ovenstående figur, vi kan se, at local_maximum er lig med 3, og som er summen af de subarray . Nu har et kig på subarrays slutter med A. vil Du bemærke, at disse subarrays kan opdeles i to dele, subarrays slutter med En (fremhævet med gult) og enkelt element, subarray En (i grøn).
lad os sige på en eller anden måde kender jeg local_ma .imum., Så vi ser, at for at beregne local_maximum, vi behøver ikke at beregne summen af alle subarrays slutter med En, da vi allerede kender resultatet fra arrays slutter med A. Bemærk, at hvis array havde det maksimale beløb, så vi kun behøver at tjekke arrays, der er fremhævet med røde pile for at beregne local_maximum. Og det fører os til det princip, som Kadanes algoritme fungerer på.
local_maximum på indeks jeg er højst En og summen af A og local_maximum i indeks i-1.,
ved Hjælp af ovenstående metode, er vi nødt til at gennemgå den matrix, bare én gang, hvilket er meget bedre end vores tidligere brute force tilgang. Eller for at være mere præcis er tidskompleksiteten af Kadanes algoritme O(n).
endelig, lad os se, hvordan alt dette ville fungere i kode.,
kode Walalkthrough
nedenfor er en meget selvforklarende implementering (i C++) af en funktion, der tager et array som et argument og returnerer summen af den maksimale subarray.
Bemærk, at i stedet for at bruge et array til at gemme local_maximums, vi er blot at gemme den seneste local_maximum i en int type variabel ‘local_max”, fordi det er, hvad vi har brug for at beregne næste local_maximum., Også, som vi bruger en variabel ‘global_ma.’ for at holde styr på den maksimale værdi af local_ma .imum, som i sidste ende kommer ud til at være den nødvendige output.
Konklusion
på Grund af den måde, denne algoritme bruger optimal delstrukturer (den maksimale subarray slutter ved hver position beregnes på en enkel måde fra en beslægtet men mindre og overlappende subproblem: den maksimale subarray slutter på den foregående position) denne algoritme kan ses som et simpelt eksempel på dynamisk programmering., Kadanes algoritme er i stand til at finde den maksimale sum af en sammenhængende subarray i et array med en runtime på O(N).