Als u hier bent, dan is de kans groot dat u het “Maximum Subarray probleem” probeerde op te lossen en Kadane ‘ s algoritme tegenkwam, maar niet kon achterhalen hoe zoiets werkt. Of misschien was je het zat om Kadane ‘ s algoritme te gebruiken als een “black-box”. Of misschien wilde je het dynamische programmeeraspect ervan begrijpen. Of misschien wil je gewoon leren over een nieuw concept dat je beter kan programmeren. Wat de reden ook is, je bent hier aan het juiste adres.,
om Kadane ‘ s algoritme beter te begrijpen, zouden we eerst een korte introductie van dynamisch programmeren doorlopen. Dan zouden we kijken naar een vrij populair programmeerprobleem, het maximale Subarray probleem. We zouden zien hoe dit probleem kan worden opgelost met behulp van een brute krachtbenadering en dan zouden we proberen onze aanpak te verbeteren en met een beter algoritme te komen, aka, Kadane ‘ s algoritme.
dus, laten we beginnen.,
dynamisch programmeren
dynamisch programmeren is een methode om een complex probleem op te lossen door het op te splitsen in een verzameling eenvoudiger subproblemen, elk van deze subproblemen slechts één keer op te lossen en hun oplossingen op te slaan met behulp van een geheugengebaseerde datastructuur (array, map, enz.). Dus de volgende keer dat hetzelfde subprobleem zich voordoet, in plaats van de oplossing te herberekenen, zoekt men gewoon de eerder berekende oplossing op, waardoor rekentijd wordt bespaard.
degenen die zich het verleden niet kunnen herinneren zijn veroordeeld om het te herhalen., – Dynamic Programming
Hier is een briljante uitleg over het concept van dynamisch programmeren op Quora-Jonathan Paulson ‘ s antwoord op Hoe moet ik dynamisch programmeren uitleggen aan een 4-jarige?
hoewel er meer is aan dynamisch programmeren, zouden we verder gaan om het maximale Subarray probleem te begrijpen.
Maximum Subarray probleem
het maximum subarray probleem is de taak om de grootst mogelijke som van een aaneengesloten subarray te vinden, binnen een gegeven eendimensionale array a van getallen.,
bijvoorbeeld, voor de bovenstaande array is de aaneengesloten subarray met de grootste som, met Som 6. We zouden deze array gebruiken als ons voorbeeld voor de rest van dit artikel. Ook zouden we aannemen dat deze array nul-geïndexeerd is, dat wil zeggen -2 zou worden genoemd als het ‘0De’ element van de array enzovoort. Ook zou A de waarde op index i vertegenwoordigen.,
nu zouden we een blik werpen op een zeer voor de hand liggende oplossing voor het gegeven probleem.
Brute kracht benadering
een zeer voor de hand liggende maar niet zo goede oplossing is het berekenen van de som van elke mogelijke subarray en het maximum daarvan zou de oplossing zijn. We kunnen beginnen met index 0 en de som berekenen van elke mogelijke subarray beginnend met het element A, Zoals weergegeven in de onderstaande figuur. Dan berekenen we de som van elke mogelijke subarray beginnend met A, A enzovoort tot en met A, waarbij n de grootte van de array aangeeft (n = 9 in ons geval)., Merk op dat elk element zelf een subarray is.
We zullen noemen de maximale som van de sub-array ‘ s beginnen met Een element van de local_maximum index i. Dus na het doorlopen van alle indices, we zouden links met local_maximum voor alle indices. Tenslotte kunnen we het maximum van deze local_maximums vinden en krijgen we de uiteindelijke oplossing, d.w.z., het maximaal mogelijke bedrag. We zouden dit het global_maximum noemen.
maar je zou kunnen opmerken dat dit geen erg goede methode is, omdat naarmate de grootte van array toeneemt, het aantal mogelijke subarrays snel toeneemt, waardoor de computationele complexiteit toeneemt. Of om preciezer te zijn, als de grootte van de array n is, dan is de tijdcomplexiteit van deze oplossing O(n2), wat niet erg goed is.
Hoe kunnen we dit verbeteren? Is er een manier om het concept van dynamische programmering te gebruiken? Laten we dat uitzoeken.,
Kadane ‘ s algoritme
In deze sectie zouden we de brute force benadering die hierboven is besproken opnieuw gebruiken, maar deze keer zouden we achteruit beginnen. Hoe zou dat helpen? Eens kijken.
we zouden beginnen met het laatste element en de som berekenen van elke mogelijke subarray eindigend met het element A, Zoals getoond in de onderstaande figuur. Dan zouden we de som berekenen van elke mogelijke subarray eindigend op A, A en ga zo maar door tot A.,
laten we ons nu concentreren op de subarrays die eindigen met het element a (=-1) en a (=2) in de onderstaande figuur.,
Uit bovenstaande figuur, we zien dat het local_maximum gelijk is aan 3 wat de som is van de subarray . Kijk nu eens naar de subarrays die eindigen op A. Je zult merken dat deze subarrays in twee delen kunnen worden verdeeld, de subarrays die eindigen op A (gemarkeerd met geel) en het enkele element subarray A (in groen).
laten we zeggen dat ik het local_maximum ken., Dan zien we dat om het local_maximum te berekenen, we niet nodig hebben om de som van alle subarrays eindigend met A omdat we al weten het resultaat van arrays eindigend met A. merk op dat als array had de maximale som, dan hoeven we alleen de arrays gemarkeerd met de rode pijlen te controleren om local_maximum te berekenen. Dit leidt ons naar het principe waarop Kadane ‘ s algoritme werkt.
local_maximum bij index i is het maximum van A en de som van A en local_maximum bij index i-1.,
met Behulp van de bovenstaande methode, moeten we doorlopen de matrix slechts één keer, dat is veel beter dan onze vorige brute kracht. Of om preciezer te zijn, de tijdscomplexiteit van Kadane ‘ s algoritme is O(n).
ten slotte, laten we eens kijken hoe dit allemaal in code zou werken.,
Code Walkthrough
Hieronder is een zeer vanzelfsprekende implementatie (in C++) van een functie die een array als argument neemt en de som van de maximale subarray retourneert.
Note dat in plaats van het gebruik van een array om local_maximums op te slaan, we gewoon opslaan van de nieuwste local_maximum in een int type variabele ‘local_max’ omdat dat is wat we nodig hebben om te berekenen volgende local_maximum., Ook, omdat we een variabele ‘global_max’ gebruiken om de maximale waarde van local_maximum bij te houden, wat uiteindelijk de vereiste uitvoer blijkt te zijn.
conclusie
vanwege de manier waarop dit algoritme optimale substructuren gebruikt (de maximale subarray die eindigt op elke positie wordt op een eenvoudige manier berekend uit een gerelateerd maar kleiner en overlappend subprobleem: de maximale subarray die eindigt op de vorige positie) kan dit algoritme worden gezien als een eenvoudig voorbeeld van dynamisch programmeren., Kadane ‘ s algoritme is in staat om de maximale som van een aaneengesloten subarray te vinden in een array met een runtime van O(n).