Pokud jste zde, pak šance jsou, že jste se snažili vyřešit „Maximální Pole Problém“ a narazil si Kadane Algoritmus, ale nemohl přijít na to, jak něco takového funguje. Nebo jste možná byli unaveni použitím Kadaneho algoritmu jako“černé skříňky“. Nebo možná jste chtěli pochopit dynamický programovací aspekt. Nebo se možná jen chcete dozvědět o novém konceptu, který vám může zlepšit programování. Ať už je důvod jakýkoli, jste na správném místě.,
abychom lépe porozuměli Kadaneovu algoritmu, nejprve bychom prošli krátkým zavedením dynamického programování. Pak bychom se podívali na docela populární programovací problém, maximální problém Subarray. Viděli bychom, jak lze tento problém vyřešit pomocí přístupu hrubé síly, a pak bychom se pokusili zlepšit náš přístup a přijít s lepším algoritmem, aka, Kadaneův algoritmus.
takže se do toho dostaneme.,
Dynamické Programování
Dynamické Programování je metodou pro řešení složitého problému tím, rozebrat to do sbírky jednodušší dílčích problémů, řešení každé z těchto dílčích problémů jen jednou, a ukládání jejich řešení pomocí paměti založené datové struktury (pole, mapa, atd.). Takže příště stejný dílčí problém nastane, namísto přepočítání jeho řešení, Jeden jednoduše vyhledá dříve vypočtené řešení, čímž šetří čas výpočtu.
ti, kteří si minulost nepamatují, jsou odsouzeni k jejímu opakování., — Dynamické Programování,
Tady je brilantní vysvětlení na koncept Dynamického Programování na Quora — Jonathan Paulson je odpověď na to, Jak mám vysvětlit, dynamické programování 4-rok-starý?
přestože existuje více dynamického programování, posunuli bychom se vpřed, abychom pochopili maximální problém Subarray.
Maximální Pole Problém
maximální pole problémem je úkol najít největší součet souvislé pole, v daném jednorozměrné pole čísel.,
například, pro pole uvedených výše, sousedící pole s největší částka , se součtem 6. Toto pole bychom použili jako náš příklad pro zbytek tohoto článku. Také bychom předpokládat, že toto pole musí být nulové indexovány, tj. -2 by být nazýván jako ‚0‘ prvek pole a tak dále. Také a by představovalo hodnotu v indexu i.,
nyní bychom se podívali na velmi zřejmé řešení daného problému.
Přístup Hrubou Silou
Jeden velmi zřejmé, ale není to tak dobré řešení je vypočítat součet všech možných pole a maximální těch by bylo řešení. Můžeme začít od indexu 0 a vypočítat součet všech možných subarray počínaje prvkem a, jak je znázorněno na obrázku níže. Pak bychom mohli vypočítat součet všech možných pole počínaje, a tak dále až k, kde n označuje velikost pole (n = 9 v našem případě)., Všimněte si, že každý jednotlivý prvek je subarray sám.
Budeme nazývat maximální součet subarrays začíná s prvkem A local_maximum na indexu i. Tedy poté, co šel přes všechny indexy, zůstala by nám local_maximum pro všechny indexy. Nakonec můžeme najít maximum těchto local_maximums a dostaneme konečné řešení, tj., maximální možný součet. Nazvali bychom to global_maximum.
Ale můžete si všimnout, že to není moc dobrá metoda, protože jako velikost pole se zvyšuje, počet možných subarrays rychle zvyšuje, čímž se zvyšuje výpočetní náročnost. Nebo přesněji, pokud je velikost pole n, pak časová složitost tohoto řešení je O(n2), což není příliš dobré.
Jak to můžeme zlepšit? Existuje nějaký způsob, jak použít koncept dynamického programování? Pojďme to zjistit.,
Kadane Algoritmus
V této části bychom použít hrubou silou přístup uvedeno výše znovu, ale tentokrát bychom začít dozadu. Jak by to pomohlo? Podívejme se.
měli Bychom začít od posledního prvku a výpočet součet všech možných pole konče prvek, jak je znázorněno na obrázku níže. Pak bychom spočítali součet všech možných subarray končících A, A a tak dále až a.,
Nyní se pojďme zaměřit na subarrays konče prvek (=-1) a (=2) je znázorněno na obrázku níže.,
Z obrázku výše, vidíme, že local_maximum je rovna 3, což je součet pole . Nyní se podívejte na subarrays končí s. A. všimněte Si, že tyto subarrays může být rozdělena do dvou částí, subarrays konče (zvýrazněno žlutě) a jeden prvek pole (v zelené).
řekněme, že nějak znám local_maximum., Pak vidíme, že pro výpočet local_maximum, nepotřebujeme k výpočtu součtu všech subarrays konče, neboť již víme, že výsledek z polí končí s. A. Všimněte si, že pokud pole má maximální částku, pak jsme pouze potřeba zkontrolovat pole zvýrazněny červenými šipkami pro výpočet local_maximum. A to nás vede k principu, na kterém Kadaneův algoritmus funguje.
local_maximum at index I je maximum a a součet a a local_maximum at index i-1.,
za Použití výše uvedené metody, musíme iterovat přes pole jen jednou, což je mnohem lepší než naše předchozí přístup hrubou silou. Nebo přesněji, časová složitost Kadaneho algoritmu je O (n).
nakonec se podívejme, jak by to všechno fungovalo v kódu.,
Kód Návod
Níže je velmi self-vysvětlující provádění (v C++) funkce, která bere pole jako argument a vrátí součet maximální pole.
Všimněte si, že namísto použití pole pro uložení local_maximums, jsme prostě ukládání nejnovější local_maximum v int proměnnou typu ‚local_max, protože to je to, co potřebujeme pro výpočet další local_maximum., Také, jak jsme pomocí proměnné ‚global_max‘ sledovat maximální hodnotu local_maximum, které na konci vyjde na požadovaný výstup.
Závěr
Kvůli tomu, jak tento algoritmus používá optimální podstruktury (maximální pole končí na každou pozici se vypočítá jednoduchým způsobem od spřízněné, ale menší a překrývající se trápím: maximální pole končí na předchozí pozici) tento algoritmus může být viděn jako jednoduchý příklad dynamického programování., Kadane algoritmus je schopen nalézt maximální součet souvislé pole v poli s runtime o(n).