streamalism.org

1. Prehľad

Problémom maximálneho podradeného poľa je úloha nájsť sériu súvislých prvkov s maximálnym súčtom v ľubovoľnom danom poli.

Napríklad v nasledujúcom poli zvýraznená podskupina má maximálny súčet (6):

V tomto výučbe sa pozrieme na dve riešenia hľadania maximálneho podoblastia v poli. Jeden z nich navrhneme O (n) časová a priestorová zložitosť.

2. Algoritmus hrubej sily

Hrubá sila je iteračný prístup k riešeniu problému. Vo väčšine prípadov riešenie vyžaduje množstvo iterácií cez dátovú štruktúru. V nasledujúcich niekoľkých častiach použijeme tento prístup na vyriešenie problému s maximálnym podsúborom.

2.1. Prístup

Všeobecne povedané, prvé riešenie, ktoré vás napadne, je vypočítať súčet všetkých možných podradených polí a vrátiť ten s maximálnym súčtom.

Na začiatok vypočítame súčet každého podoblasti, ktoré začína na indexe 0. A podobne, nájdeme všetky podskupiny začínajúce pri každom indexe od 0 do n-1 kde n je dĺžka poľa:

Takže začneme indexom 0 a v iterácii pridajte každý prvok k priebežnej sume. Budeme tiež sledovať maximálnu sumu, ktorá sa doteraz videla. Táto iterácia je zobrazená na ľavej strane obrázka vyššie.

Na pravej strane obrázku vidíme iteráciu, ktorá začína na indexe 3. V poslednej časti tohto obrázka máme podradnú sústavu s maximálnym súčtom medzi indexom 3 a 6.

Avšak náš algoritmus bude naďalej hľadať všetky podradené polia začínajúce na indexoch medzi 0 a n-1.

2.2. Implementácia

Pozrime sa teraz, ako môžeme implementovať toto riešenie v Jave:

public int maxSubArray (int [] nums) {int n = nums.length; int maximumSubArraySum = Integer.MIN_VALUE; int start = 0; int koniec = 0; for (int left = 0; left <n; left ++) {int runningWindowSum = 0; pre (int vpravo = vľavo; vpravo maximumSubArraySum) {maximumSubArraySum = runningWindowSum; štart = vľavo; koniec = pravý; }}} logger.info ("Nájdený maximálny podskupina medzi {} a {}", začiatok, koniec); návrat maximumSubArraySum; }

Podľa očakávania aktualizujeme maximumSubArraySum ak je súčasná suma vyššia ako predchádzajúca maximálna suma. Je pozoruhodné, potom tiež aktualizujeme začať a koniec zistiť indexové umiestnenia tohto podradeného poľa.

2.3. Zložitosť

Všeobecne povedané, riešenie hrubou silou iteruje cez pole mnohokrát, aby bolo možné získať všetky možné riešenia. To znamená, že čas potrebný na toto riešenie kvadraticky rastie s počtom prvkov v poli. To nemusí byť problém pre polia malých rozmerov. Ale ako veľkosť poľa rastie, toto riešenie nie je efektívne.

Po kontrole kódu tiež zistíme, že sú vnorené dva pre slučky. Preto môžeme konštatovať, že časová zložitosť tohto algoritmu je O (n2).

V ďalších častiach budeme tento problém riešiť v O (n) zložitosť pomocou dynamického programovania.

3. Dynamické programovanie

Dynamické programovanie rieši problém rozdelením na menšie podproblémy. Je to veľmi podobné technike riešenia algoritmov rozdelenia a dobývania. Hlavným rozdielom však je, že dynamické programovanie vyrieši podproblém iba raz.

Potom uloží výsledok tohto čiastkového problému a neskôr ho znovu použije na riešenie ďalších súvisiacich čiastkových problémov. Tento proces sa nazýva memoizácia.

3.1. Kadanov algoritmus

Kadanov algoritmus je populárnym riešením problému maximálnej podoblasti a toto riešenie je založené na dynamickom programovaní.

Najdôležitejšia výzva pri riešení dynamického programovania problémom je nájsť optimálne podproblémy.

3.2. Prístup

Poďme tento problém pochopiť inak:

Na vyššie uvedenom obrázku predpokladáme, že maximálna podoblasť končí na poslednom mieste indexu. Maximálny súčet čiastkového poľa bude preto:

maximumSubArraySum = max_so_far + arr [n-1]

max_so_far je maximálny súčet čiastkovej sústavy, ktorá končí na indexe n-2. To je tiež zobrazené na obrázku vyššie.

Teraz môžeme tento predpoklad použiť na akýkoľvek index v poli. Napríklad maximálny súčet čiastkového poľa, ktorý končí na n-2 možno vypočítať ako:

maximumSubArraySum [n-2] = max_so_far [n-3] + arr [n-2]

Preto môžeme konštatovať, že:

maximumSubArraySum [i] = maximumSubArraySum [i-1] + arr [i]

Teraz, keď je každý prvok v poli špeciálnym podoblastím veľkosti jeden, musíme tiež skontrolovať, či je prvok väčší ako samotný maximálny súčet:

maximumSubArraySum [i] = Max (arr [i], maximumSubArraySum [i-1] + arr [i])

Pri pohľade na tieto rovnice vidíme, že pri každom indexe poľa musíme nájsť maximálny súčet čiastkových polí. Náš problém sme teda rozdelili na n podproblémy. Maximálnu sumu môžeme nájsť pri každom indexe opakovaním poľa iba raz:

Zvýraznený prvok zobrazuje aktuálny prvok v iterácii. Pri každom indexe použijeme pre výpočet hodnoty rovnicu odvodenú skôr max_ending_here. To nám pomáha pri identifikácii či by sme mali zahrnúť aktuálny prvok do podoblasti alebo založiť novú podoblasť začínajúcu týmto indexom.

Ďalšia premenná, max_so_far sa používa na uloženie maximálneho súčtu podskupiny zisteného počas iterácie. Akonáhle iterujeme posledný index, max_so_far uloží súčet maximálneho čiastkového poľa.

3.3. Implementácia

Opäť sa pozrime, ako môžeme teraz implementovať Kadaneov algoritmus v Jave podľa vyššie uvedeného prístupu:

public int maxSubArraySum (int [] arr) {int size = arr.length; int start = 0; int koniec = 0; int maxSoFar = 0, maxEndingHere = 0; for (int i = 0; i maxEndingHere + arr [i]) {start = i; maxEndingHere = arr [i]; } else maxEndingHere = maxEndingHere + arr [i]; if (maxSoFar <maxEndingHere) {maxSoFar = maxEndingHere; koniec = i; }} logger.info ("Nájdený maximálny podskupina medzi {} a {}", začiatok, koniec); návrat maxSoFar; }

Tu sme aktualizovali začať a koniec nájsť maximálne indexy podradenej sústavy.

3.4. Zložitosť

Pretože pole musíme iterovať iba raz, časová zložitosť tohto algoritmu je O (n).

Ako teda vidíme, čas, ktorý toto riešenie vyžaduje, rastie lineárne s počtom prvkov v poli. Následne je to efektívnejšie ako prístup hrubou silou, o ktorom sme hovorili v poslednej časti.

4. Záver

V tomto rýchlom výučbe sme popísali dva spôsoby riešenia problému s maximálnym podsúborom.

Najskôr sme preskúmali prístup hrubou silou a videli sme, že toto iteračné riešenie vyústilo do kvadratického času. Neskôr sme potom diskutovali o Kadanovom algoritme a pomocou dynamického programovania sme problém vyriešili v lineárnom čase.

Celý zdrojový kód článku je ako vždy k dispozícii na GitHub.