Ha itt van, akkor valószínű, hogy megpróbálta megoldani a” maximális Subarray problémát”, és találkozott Kadane algoritmusával, de nem tudta kitalálni, hogyan működik valami ilyesmi. Vagy talán belefáradt, hogy Kadane algoritmusát “fekete dobozként”használja. Vagy talán meg akarta érteni annak dinamikus programozási aspektusát. Vagy talán csak egy új koncepciót szeretne megismerni, amely jobbá teheti a programozást. Bármi is legyen az oka, a megfelelő helyre jöttél.,
A Kadane algoritmusának jobb megértése érdekében először a dinamikus programozás rövid bevezetésén megyünk keresztül. Ezután egy nagyon népszerű programozási problémát, a maximális Alarray problémát vizsgálnánk. Megnéznénk, hogyan oldható meg ez a probléma egy nyers erő megközelítés segítségével, majd megpróbálnánk javítani a megközelítésünket, és egy jobb algoritmussal, más néven Kadane algoritmusával állnánk elő.
tehát menjünk bele.,
dinamikus programozás
a dinamikus programozás egy összetett probléma megoldására szolgáló módszer, egyszerűbb alproblémák gyűjteményére bontva, mindegyik alproblémát csak egyszer megoldva, megoldásaikat memória alapú adatstruktúra (tömb, térkép stb.) segítségével tárolva.). Tehát a következő alkalommal, amikor ugyanaz az alprobléma jelentkezik, a megoldás újraszámítása helyett egyszerűen felnéz a korábban kiszámított megoldásra, ezáltal megtakarítva a számítási időt.
azok, akik nem emlékeznek a múltra, elítélik annak megismétlését., – Dinamikus programozás
íme egy ragyogó magyarázat a dinamikus programozás fogalmáról a Quora-on-Jonathan Paulson válasza arra, hogyan magyarázzam el a dinamikus programozást egy 4 éves korúnak?
bár van még dinamikus programozás, mi lenne előrelépni, hogy megértsék a maximális Subarray probléma.
maximális Subarray probléma
a maximális subarray probléma az a feladat, hogy megtaláljuk a legnagyobb lehetséges összege egy összefüggő subarray, egy adott egydimenziós tömb a számok.,
például a tömb adott felett, a szomszédos subarray a legnagyobb összeg , amelynek összege 6. Mi lenne használni ezt a tömböt, mint a példa a többi ezt a cikket. Azt is feltételeznénk, hogy ez a tömb nulla indexelt, azaz -2 a tömb “0.” elemének nevezhető stb. Továbbá, az a az I. index értékét képviseli.,
most megnéznénk egy nagyon nyilvánvaló megoldást az adott problémára.
Brute Force Approach
egy nagyon nyilvánvaló, de nem olyan jó megoldás az, hogy kiszámoljuk az összes lehetséges alarray összegét, és ezek közül a maximális lenne a megoldás. A 0. indexből kiindulva kiszámolhatjuk az összes lehetséges részarány összegét az a elemtől kezdve, az alábbi ábrán látható módon. Ezután kiszámítjuk az összes lehetséges alrend összegét, kezdve az A-val, stb. Az A-ig, ahol n A tömb méretét jelöli (esetünkben n = 9)., Vegye figyelembe, hogy minden egyes elem maga a részegység.
hívjuk a maximális összege subarrays kezdve elem a local_maximum az index azt. Így, miután átment az indexek, mi lenne maradt local_maximum az indexek. Végül megtaláljuk a maximumot ezekből a lokális_maximumokból, és megkapjuk a végső megoldást, azaz, a maximális összeg lehetséges. Ezt neveznénk global_maximumnak.
de előfordulhat, hogy ez nem egy nagyon jó módszer, mert a tömb méretének növekedésével a lehetséges subarraysok száma gyorsan növekszik, ezáltal növelve a számítási komplexitást. Vagy pontosabban, ha a tömb mérete n, akkor ennek a megoldásnak az idő összetettsége O (n2), ami nem túl jó.
hogyan javíthatjuk ezt? Van-e mód a dinamikus programozás fogalmának használatára? Derítsük ki.,
Kadane algoritmusa
ebben a szakaszban a fent tárgyalt brute force megközelítést alkalmaznánk újra, de ezúttal visszafelé indulnánk. Ez hogyan segítene? Lássuk csak.
az utolsó elemből indulunk ki, és kiszámítjuk az összes lehetséges részösszeget, amely az ” a ” elemmel végződik, az alábbi ábrán látható módon. Ezután kiszámítjuk az összes lehetséges részösszeget, amely A-VAL, A-val és így tovább A-ig végződik.,
most összpontosítsunk az A (=-1) és a (=2) elemre végződő alarráikra az alábbi ábrán.,
A fenti ábra szerint, azt látjuk, hogy a local_maximum egyenlő 3, amely az összeget a subarray . Most nézd meg a subarrays végződő A. észre fogod venni, hogy ezek subarrays lehet osztani két részre, a subarrays végződő (sárga színnel kiemelve) és az egyetlen elem subarray A (zöld).
mondjuk valahogy ismerem a local_maximumot., Aztán látjuk, hogy a local_maximum kiszámításához nem kell kiszámítanunk az A-val végződő összes subarrays összegét, mivel már ismerjük az A-val végződő tömbök eredményét.vegye figyelembe, hogy ha a tömb volt a maximális összeg, akkor csak a piros nyilakkal kiemelt tömböket kell ellenőriznünk a local_maximum kiszámításához. Ez pedig arra az elvre vezet, amelyen Kadane algoritmusa működik.
local_maximum az I. Indexnél az A és local_maximum összege az I-1 Indexnél.,
a fenti módszer, meg kell halad végig a tömb csak egyszer, ami sokkal jobb, mint a korábbi nyers erő megközelítés. Vagy pontosabban, Kadane algoritmusának idő összetettsége O (n).
végül nézzük meg, hogyan működik ez az egész kódban.,
Code Walkthrough
Az alábbiakban egy nagyon sok magától értetődő végrehajtása (C++) egy függvény, amely úgy egy tömb, mint egy érv, és visszatér az összeg a maximális subarray.
/ div >
megjegyezzük, hogy ahelyett, hogy egy tömb tárolására local_maximum, mi egyszerűen tárolja a legújabb local_maximum int típusú változó “local_max”, mert ez az, amit meg kell számítani következő local_maximum., Továbbá, mivel egy “global_max” változót használunk a local_maximum maximális értékének nyomon követésére, amely végül a szükséges kimenetnek felel meg.
következtetés
mivel ez az algoritmus optimális alszerkezeteket használ (az egyes pozíciókra végződő maximális alrendet egyszerű módon számítják ki egy kapcsolódó, de kisebb és átfedő alproblemből:az előző pozícióra végződő maximális alrendezés) ez az algoritmus a dinamikus programozás egyszerű példájaként tekinthető., Kadane algoritmusa képes megtalálni az egybefüggő subarray maximális összegét egy o(n) futásidejű tömbben.