streamalism.org

1. Áttekintés

A maximális alray probléma egy olyan feladat, hogy megtalálja a szomszédos elemek sorozatát a maximális összeggel az adott tömbben.

Például az alábbi tömbben a kiemelt részrajz maximális összege (6):

Ebben az oktatóanyagban két megoldást fogunk megvizsgálni a tömb maximális részterületének megtalálásához. Az egyiket megtervezzük Tovább) idő és tér összetettsége.

2. Brute Force algoritmus

A nyers erő iteratív megközelítés a probléma megoldására. A legtöbb esetben a megoldás többszörös ismétlést igényel egy adatszerkezet felett. A következő néhány szakaszban ezt a megközelítést alkalmazzuk a maximális részarakter probléma megoldására.

2.1. Megközelítés

Általánosságban elmondható, hogy az első megoldás, ami eszembe jut, az, hogy kiszámoljuk az összes lehetséges részarány összegét, és visszaadjuk azt, amelynek a maximális összege van.

Először kiszámoljuk az összes részarány összegét, amely a 0 indexen kezdődik. És hasonlóan, meg fogjuk találni az összes alsávot minden indextől kezdve 0 nak nek n-1 hol n a tömb hossza:

Tehát az indexnél kezdjük 0 és adjon hozzá minden elemet az iteráció futó összegéhez. Szintén jól tartsa nyilván az eddig látott maximális összeget. Ez az iteráció a fenti kép bal oldalán látható.

A kép jobb oldalán láthatjuk az indexről induló iterációt 3. A kép utolsó részében megkapjuk az alrészt az index közötti maximális összeggel 3 és 6.

Azonban, algoritmusunk továbbra is megtalálja az összes alsávot a között lévő indexektől kezdve 0 és n-1.

2.2. Végrehajtás

Most nézzük meg, hogyan tudjuk megvalósítani ezt a megoldást a Java-ban:

public int maxSubArray (int [] nums) {int n = nums.hossz; int maximumSubArraySum = Egész.MIN_VALUE; int kezdet = 0; int vége = 0; mert (int bal = 0; bal <n; bal ++) {int runningWindowSum = 0; for (int jobb = bal; jobb maximumSubArraySum) {maximumSubArraySum = runningWindowSum; start = bal; vég = jobb; }}} logger.info ("Megtalált maximális alrész {} és {} között, kezdet, vég); return maximumSubArraySum; }

A várakozásoknak megfelelően frissítjük a maximumSubArraySum ha az aktuális összeg meghaladja az előző maximális összeget. Nevezetesen, ezután frissítjük a Rajt és vége hogy megtudja ennek az alrésznek az index helyeit.

2.3. Bonyolultság

Általánosságban elmondható, hogy a nyers erő megoldása sokszor ismétlődik a tömbön, hogy minden lehetséges megoldást megkapjon. Ez azt jelenti, hogy a megoldás által igénybe vett idő kvadratikusan növekszik a tömbben lévő elemek számával együtt. Ez nem jelenthet problémát kis méretű tömbök esetén. De a tömb méretének növekedésével ez a megoldás nem hatékony.

A kód megvizsgálásával azt is láthatjuk, hogy két beágyazott van mert hurkok. Ezért arra a következtetésre juthatunk, hogy ennek az algoritmusnak az időbeli összetettsége igen O (n2).

A későbbi szakaszokban ezt a problémát itt oldjuk meg Tovább) komplexitás dinamikus programozással.

3. Dinamikus programozás

A dinamikus programozás megoldja a problémát azáltal, hogy kisebb részproblémákra osztja. Ez nagyon hasonlít az osztani és meghódítani algoritmus-megoldási technikára. A fő különbség azonban az, hogy a dinamikus programozás csak egyszer oldja meg a részproblémát.

Ezután eltárolja ennek az alproblémának az eredményét, majd később felhasználja ezt az eredményt más kapcsolódó részproblémák megoldására. Ezt a folyamatot memoizálásnak nevezik.

3.1. Kadane algoritmusa

Kadane algoritmusa népszerű megoldás a maximális részarakter problémára, és ez a megoldás dinamikus programozáson alapul.

A dinamikus programozás megoldásának legfontosabb kihívása probléma az optimális részproblémák megtalálása.

3.2. Megközelítés

Értsük meg ezt a problémát másképp:

A fenti képen feltételezzük, hogy a maximális részrajz az utolsó index helyén ér véget. Ezért az alrész maximális összege a következő lesz:

maximumSubArraySum = max_so_far + arr [n-1]

max_so_far az indexen végződő részterület maximális összege n-2. Ezt mutatja a fenti kép is.

Ezt a feltételezést alkalmazhatjuk a tömb bármely indexére. Például a maximális részösszeg, amelynek vége: n-2 kiszámítható:

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

Ezért arra a következtetésre juthatunk, hogy:

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

Most, mivel a tömbben minden elem egy speciális méretű alrészlet, azt is ellenőriznünk kell, hogy egy elem nagyobb-e, mint maga a maximális összeg:

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

Ezeket az egyenleteket megnézve láthatjuk, hogy a tömb minden indexénél meg kell találnunk a maximális részösszetétel összegét. Így felosztottuk a problémánkat n részproblémák. Megtalálhatjuk a maximális összeget minden indexnél, ha a tömböt csak egyszer iteráljuk:

A kiemelt elem az iteráció aktuális elemét mutatja. Minden indexnél a korábban kapott egyenletet alkalmazzuk az érték kiszámításához max_ending_here. Ez segít nekünk az azonosításban be kell-e vonni az aktuális elemet az alrészbe, vagy ebből az indexből kiindulva indítunk-e új alrészt.

Egy másik változó, max_so_far az iteráció során talált maximális részösszeg tárolására szolgál. Amint iterálunk az utolsó index felett, max_so_far a maximális részarány összegét tárolja.

3.3. Végrehajtás

Ismét lássuk, hogyan tudjuk most megvalósítani a Kadane algoritmust a Java-ban, a fenti megközelítést követve:

public int maxSubArraySum (int [] arr) {int méret = arr.length; int kezdet = 0; int vége = 0; int maxSoFar = 0, maxEndingHere = 0; for (int i = 0; i maxEnding Here + arr [i]) {start = i; maxEndingHere = arr [i]; } else maxEndingHere = maxEndingHere + arr [i]; if (maxSoFar <maxEndingHere) {maxSoFar = maxEndingHere; vég = i; }} logger.info ("Megtalált maximális részrajz {} és {} között", kezdet, vég); return maxSoFar; }

Itt frissítettük a Rajt és vége hogy megtalálja a maximális részrajzi indexeket.

3.4. Bonyolultság

Mivel csak egyszer kell iterálnunk a tömböt, ennek az algoritmusnak az időbeli összetettsége igen Tovább).

Tehát, mint láthatjuk, ennek a megoldásnak az ideje lineárisan növekszik a tömb elemeinek számával. Következésképpen hatékonyabb, mint az utolsó szakaszban tárgyalt durva erő megközelítés.

4. Következtetés

Ebben a gyors bemutatóban két módszert írtunk le a maximális alrét probléma megoldására.

Először egy nyers erő megközelítést tártunk fel, és láttuk, hogy ez az iteratív megoldás másodfokú időt eredményezett. Később aztán megvitattuk a Kadane algoritmust, és dinamikus programozással oldottuk meg a problémát lineáris időben.

Mint mindig, a cikk teljes forráskódja elérhető a GitHubon.