om du är här är chansen att du försökte lösa det ”maximala Subarrayproblemet” och kom över Kadanes algoritm men kunde inte räkna ut hur något sådant fungerar. Eller kanske var du trött på att använda Kadanes algoritm som en”svart låda”. Eller kanske du ville förstå den dynamiska programmeringsaspekten av den. Eller kanske du bara vill lära dig om ett nytt koncept som kan göra dig bättre på programmering. Oavsett orsaken, har du kommit till rätt ställe.,
för att bättre förstå Kadanes algoritm skulle vi först gå igenom en kort introduktion av dynamisk programmering. Då skulle vi titta på ett ganska populärt programmeringsproblem, det maximala Subarrayproblemet. Vi skulle se hur detta problem kan lösas med hjälp av ett brute force-tillvägagångssätt och då skulle vi försöka förbättra vårt tillvägagångssätt och komma med en bättre algoritm, aka, Kadanes algoritm.
så, låt oss komma in i det.,
dynamisk programmering
dynamisk programmering är en metod för att lösa ett komplext problem genom att bryta ner det i en samling enklare underproblem, lösa var och en av dessa underproblem bara en gång och lagra sina lösningar med hjälp av en minnesbaserad datastruktur (array, karta, etc.). Så nästa gång samma delproblem uppstår, istället för att omberäkna sin lösning, ser man helt enkelt upp den tidigare beräknade lösningen och sparar därmed beräkningstiden.
de som inte kommer ihåg det förflutna är dömda att upprepa det., — Dynamisk programmering
här är en lysande förklaring på begreppet dynamisk programmering på Quora-Jonathan Paulsons svar på hur ska jag förklara dynamisk programmering till en 4-årig?
även om det finns mer till dynamisk programmering, skulle vi gå vidare för att förstå det maximala Subarrayproblemet.
maximalt Subarrayproblem
det maximala subarrayproblemet är uppgiften att hitta den största möjliga summan av en sammanhängande subarray, inom en given endimensionell array a av siffror.,
till exempel, för matrisen som anges ovan, är den angränsande subarrayen med den största summan , med summan 6. Vi skulle använda denna array som vårt exempel för resten av den här artikeln. Vi skulle också anta att denna array är nollindexerad, dvs -2 skulle kallas som ” 0th ” – elementet i matrisen och så vidare. A skulle också representera värdet vid index i.,
nu skulle vi ta en titt på en mycket uppenbar lösning på det givna problemet.
Brute Force Approach
en mycket uppenbar men inte så bra lösning är att beräkna summan av alla möjliga subarray och det maximala av dem skulle vara lösningen. Vi kan börja från index 0 och beräkna summan av varje möjlig subarray som börjar med elementet A, som visas i figuren nedan. Då skulle vi beräkna summan av varje möjlig subarray som börjar med A, A och så vidare upp till A, där n betecknar storleken på matrisen (n = 9 i vårt fall)., Observera att varje enskilt element är en subarray själv.
Vi kommer att ringa den maximala summan av subarrays som börjar med element a local_maximum vid index i. således efter att ha gått igenom alla index, skulle vi vara kvar med local_maximum för alla index. Slutligen kan vi hitta maximalt av dessa local_maximums och vi skulle få den slutliga lösningen, dvs, den maximala summan möjligt. Vi skulle kalla detta global_maximum.
men du kanske märker att detta inte är en mycket bra metod eftersom storleken på arrayen ökar, antalet möjliga subarrays ökar snabbt, vilket ökar beräkningskomplexiteten. Eller för att vara mer exakt, om storleken på matrisen är n, är tidskomplexiteten för denna lösning O(n2) vilket inte är så bra.
hur kan vi förbättra detta? Finns det något sätt att använda begreppet dynamisk programmering? Låt oss ta reda på det.,
Kadanes algoritm
i det här avsnittet skulle vi använda brute force-metoden som diskuterades ovan igen, men den här gången skulle vi börja bakåt. Hur skulle det hjälpa? Få se.
vi skulle börja från det sista elementet och beräkna summan av varje möjlig subarray som slutar med elementet A, som visas i figuren nedan. Då skulle vi beräkna summan av alla möjliga subarray som slutar med A, A och så vidare upp till A.,
låt oss nu fokusera på subarrayerna som slutar med elementet A (=-1) och A (=2) som visas i figuren nedan.,
från figuren ovan ser vi att local_maximum är lika med 3, vilket är summan av subarrayen . Nu ta en titt på subarrays slutar med A. Du kommer att märka att dessa subarrays kan delas upp i två delar, subarrays slutar med en (markerad med gul) och det enda elementet subarray A (I grönt).
låt oss säga att jag på något sätt känner till local_maximum., Då ser vi att för att beräkna local_maximum behöver vi inte beräkna summan av alla subarrays som slutar med A eftersom vi redan vet resultatet från arrays som slutar med A. Observera att om array hade maximal summa, behöver vi bara kontrollera arrayerna markerade med de röda pilarna för att beräkna local_maximum. Och detta leder oss till principen som Kadanes algoritm fungerar på.
local_maximum vid index i är maximalt A och summan av A och local_maximum vid index i-1.,
med hjälp av ovanstående metod måste vi iterera genom matrisen bara en gång, vilket är mycket bättre än vårt tidigare brute force-tillvägagångssätt. Eller för att vara mer exakt är tidskomplexiteten hos Kadanes algoritm O(n).
slutligen, låt oss se hur allt detta skulle fungera i kod.,
kod genomgång
nedan är en mycket självförklarande implementering (i C++) av en funktion som tar en array som ett argument och Returnerar summan av den maximala subarrayen.
Observera att i stället för att använda en array för att lagra local_maximums lagrar vi helt enkelt senaste local_maximum i en int typ variabel ”local_max” eftersom det är vad vi behöver för att beräkna nästa local_maximum., Också, som vi använder en variabel ”global_max” för att hålla reda på det maximala värdet av local_maximum, som i slutändan kommer ut att vara den önskade utgången.
Slutsats
på Grund av det sätt på vilket denna algoritm används optimalt understrukturer (maximal subarray slutar på varje position är beräknat på ett enkelt sätt från en närstående, men mindre och överlappande subproblem: den maximala subarray slutar vid tidigare position) denna algoritm kan ses som ett enkelt exempel av dynamisk programmering., Kadanes algoritm kan hitta den maximala summan av en angränsande subarray i en array med en runtime av O(n).