streamalism.org

1. Overzicht

Het maximale subarray-probleem is een taak om de reeks aaneengesloten elementen met de maximale som in een gegeven array te vinden.

Bijvoorbeeld, in de onderstaande array, de gemarkeerde submatrix heeft de maximale som (6):

In deze zelfstudie bekijken we twee oplossingen voor het vinden van de maximale submatrix in een array. Een daarvan zullen we ontwerpen Aan) tijd en ruimte complexiteit.

2. Brute Force-algoritme

Brute kracht is een iteratieve benadering om een ​​probleem op te lossen. In de meeste gevallen vereist de oplossing een aantal iteraties over een datastructuur. In de volgende secties passen we deze benadering toe om het maximale subarrayprobleem op te lossen.

2.1. Nadering

Over het algemeen is de eerste oplossing die in je opkomt, de som van elke mogelijke submatrix te berekenen en die met de maximale som te retourneren.

Om te beginnen berekenen we de som van elke submatrix die begint bij index 0. En op dezelfde manier, we vinden alle subarrays vanaf elke index 0 naar n-1 waar n is de lengte van de array:

Dus we beginnen bij index 0 en voeg elk element toe aan de lopende som in de iteratie. We zullen ook houd de maximale som bij die tot nu toe is gezien. Deze iteratie wordt aan de linkerkant van de afbeelding hierboven weergegeven.

Aan de rechterkant van de afbeelding kunnen we de iteratie zien die begint bij index 3. In het laatste deel van deze afbeelding hebben we de submatrix met de maximale som tussen index 3 en 6.

Echter, ons algoritme zal doorgaan met het vinden van alle subarrays beginnend bij indices tussen 0 en n-1.

2.2. Implementatie

Laten we nu kijken hoe we deze oplossing in Java kunnen implementeren:

openbare int maxSubArray (int [] nums) {int n = nums.length; int maximumSubArraySum = Geheel getal.MIN_VALUE; int start = 0; int end = 0; for (int left = 0; left <n; left ++) {int runningWindowSum = 0; for (int right = left; right maximumSubArraySum) {maximumSubArraySum = runningWindowSum; start = links; einde = rechts; }}} logger.info ("Maximale submatrix gevonden tussen {} en {}", begin, einde); retourneer maximumSubArraySum; }

Zoals verwacht updaten we het maximumSubArraySum als het huidige bedrag hoger is dan het vorige maximumbedrag. Met name we updaten dan ook het begin en einde om de indexlocaties van deze subarray te achterhalen.

2.3. Complexiteit

Over het algemeen itereert de brute force-oplossing vele malen over de array om elke mogelijke oplossing te krijgen. Dit betekent dat de tijd die deze oplossing nodig heeft kwadratisch groeit met het aantal elementen in de array. Dit is misschien geen probleem voor arrays met een klein formaat. Maar naarmate de array groter wordt, is deze oplossing niet efficiënt.

Door de code te inspecteren, kunnen we ook zien dat er twee genest zijn voor lussen. Daarom kunnen we concluderen dat de tijdcomplexiteit van dit algoritme dat is O (n2).

In de latere secties zullen we dit probleem oplossen in Aan) complexiteit met behulp van dynamische programmering.

3. Dynamisch programmeren

Dynamisch programmeren lost een probleem op door het op te splitsen in kleinere deelproblemen. Dit lijkt sterk op de techniek voor het oplossen van verdeel-en-heers-algoritmen. Het grote verschil is echter dat dynamisch programmeren een deelprobleem maar één keer oplost.

Het slaat dan het resultaat van dit subprobleem op en hergebruikt dit resultaat later om andere gerelateerde subproblemen op te lossen. Dit proces staat bekend als memoisatie.

3.1. Het algoritme van Kadane

Het algoritme van Kadane is een populaire oplossing voor het maximale subarray-probleem en deze oplossing is gebaseerd op dynamisch programmeren.

De belangrijkste uitdaging bij het oplossen van een dynamische programmering probleem is om de optimale subproblemen te vinden.

3.2. Nadering

Laten we dit probleem op een andere manier begrijpen:

In de bovenstaande afbeelding gaan we ervan uit dat de maximale subarray eindigt op de laatste indexlocatie. Daarom is de maximale som van de submatrix:

maximumSubArraySum = max_so_far + arr [n-1]

max_so_far is de maximale som van een submatrix die eindigt op index n-2. Dit is ook te zien in de afbeelding hierboven.

Nu kunnen we deze aanname toepassen op elke index in de array. Bijvoorbeeld de maximale som van de submatrix die eindigt op n-2 kan worden berekend als:

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

Daarom kunnen we concluderen dat:

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

Nu, aangezien elk element in de array een speciale subarray van grootte één is, moeten we ook controleren of een element groter is dan de maximale som zelf:

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

Door naar deze vergelijkingen te kijken, kunnen we zien dat we bij elke index van de array de maximale som van de submatrix moeten vinden. Daarom hebben we ons probleem opgedeeld in n subproblemen. We kunnen de maximale som bij elke index vinden door de array slechts één keer te herhalen:

Het gemarkeerde element toont het huidige element in de iteratie. Bij elke index passen we de eerder afgeleide vergelijking toe om een ​​waarde voor te berekenen max_ending_here. Dit helpt ons bij het identificeren of we het huidige element in de subarray moeten opnemen of een nieuwe subarray moeten starten vanaf deze index.

Een andere variabele, max_so_far wordt gebruikt om de maximale som van de submatrix op te slaan die tijdens de iteratie is gevonden. Zodra we de laatste index herhalen, max_so_far slaat de som van de maximale submatrix op.

3.3. Implementatie

Laten we nogmaals kijken hoe we nu het Kadane-algoritme in Java kunnen implementeren, volgens de bovenstaande benadering:

openbare int maxSubArraySum (int [] arr) {int size = arr.length; int start = 0; int end = 0; int maxSoFar = 0, maxEndingHere = 0; for (int i = 0; i maxEndingHere + arr [i]) {start = i; maxEndingHere = arr [i]; } anders maxEndingHere = maxEndingHere + arr [i]; if (maxSoFar <maxEndingHere) {maxSoFar = maxEndingHere; einde = i; }} logger.info ("Maximale submatrix gevonden tussen {} en {}", begin, einde); retourneer maxSoFar; }

Hier hebben we het begin en einde om de maximale subarray-indices te vinden.

3.4. Complexiteit

Omdat we de array maar één keer hoeven te herhalen, is de tijdcomplexiteit van dit algoritme Aan).

Zoals we kunnen zien, groeit de tijd die deze oplossing nodig heeft lineair met het aantal elementen in de array. Bijgevolg is het efficiënter dan de brute force-benadering die we in de vorige sectie hebben besproken.

4. Conclusie

In deze korte tutorial hebben we twee manieren beschreven om het maximale subarrayprobleem op te lossen.

Eerst onderzochten we een brute force-benadering en zagen we dat deze iteratieve oplossing resulteerde in kwadratische tijd. Later hebben we het Kadane-algoritme besproken en dynamische programmering gebruikt om het probleem in lineaire tijd op te lossen.

Zoals altijd is de volledige broncode van het artikel beschikbaar op GitHub.