Maximaal subarrayprobleem - Maximum subarray problem

Visualisatie van hoe subarrays veranderen op basis van start- en eindposities van een sample. Elke mogelijke aaneengesloten sub-array wordt weergegeven door een punt op een gekleurde lijn. De y-coördinaat van dat punt vertegenwoordigt de som van de steekproef. De x-coördinaat vertegenwoordigt het einde van het monster en het meest linkse punt op die gekleurde lijn vertegenwoordigt het begin van het monster. In dit geval is de array waaruit monsters worden genomen [2, 3, -1, -20, 5, 10].

In de informatica is het maximale som-subarrayprobleem de taak om een ​​aaneengesloten subarray met de grootste som te vinden binnen een gegeven eendimensionale array A[1...n] van getallen. Formeel is het de taak om indices en met te vinden , zodat de som ${\displaystyle ik}$${\displaystyle j}$${\ Displaystyle 1 \ leq i \ leq j \ leq n}$

${\displaystyle \sum _{x=i}^{j}A[x]}$

zo groot mogelijk is. (Sommige formuleringen van het probleem maken het ook mogelijk om de lege subarray in overweging te nemen; volgens afspraak is de som van alle waarden van de lege subarray nul.) Elk getal in de invoerarray A kan positief, negatief of nul zijn.

Voor de reeks waarden [−2, 1, −3, 4, −1, 2, 1, −5, 4] is de aangrenzende subarray met de grootste som bijvoorbeeld [4, −1, 2, 1] , met som 6.

Enkele eigenschappen van dit probleem zijn:

1. Als de array alle niet-negatieve getallen bevat, is het probleem triviaal; een maximale subarray is de gehele array.
2. Als de array alle niet-positieve getallen bevat, dan is een oplossing een willekeurige subarray van grootte 1 die de maximale waarde van de array bevat (of de lege subarray, als dat is toegestaan).
3. Meerdere verschillende subarrays kunnen dezelfde maximale som hebben.

Dit probleem kan worden opgelost met behulp van verschillende algoritmische technieken, waaronder brute kracht, verdeel en heers, dynamisch programmeren en reductie tot de kortste paden.

Geschiedenis

Het maximale subarray-probleem werd in 1977 door Ulf Grenander voorgesteld als een vereenvoudigd model voor maximale waarschijnlijkheidsschatting van patronen in gedigitaliseerde afbeeldingen.

Grenander was op zoek naar een rechthoekige subarray met maximale som, in een tweedimensionale array van reële getallen. Een brute-force-algoritme voor het tweedimensionale probleem loopt in O ( n ⁶ ) tijd; omdat dit onbetaalbaar traag was, stelde Grenander het eendimensionale probleem voor om inzicht te krijgen in de structuur ervan. Grenander heeft een algoritme afgeleid dat het eendimensionale probleem in O ( n ² ) tijd oplost , waardoor de brute force-looptijd van O ( n ³ ) wordt verbeterd. Toen Michael Shamos over het probleem hoorde, bedacht hij er van de ene op de andere dag een O ( n log n ) verdeel-en-heers-algoritme voor. Kort daarna beschreef Shamos het eendimensionale probleem en de geschiedenis ervan tijdens een seminar van de Carnegie Mellon University, bijgewoond door Jay Kadane , die binnen een minuut een O ( n )-tijd-algoritme ontwierp , dat zo snel mogelijk is. In 1982 verkreeg David Gries hetzelfde O ( n )-tijdalgoritme door Dijkstra 's "standaardstrategie" toe te passen; in 1989 leidde Richard Bird het af door puur algebraïsche manipulatie van het brute-force-algoritme met behulp van het Bird-Meertens-formalisme .

De tweedimensionale generalisatie van Grenander kan worden opgelost in O( n ³ ) tijd, hetzij door het algoritme van Kadane als subroutine te gebruiken, hetzij door een verdeel-en-heersbenadering. Iets snellere algoritmen op basis van afstandsmatrixvermenigvuldiging zijn voorgesteld door Tamaki & Tokuyama (1998) en door Takaoka (2002) . Er zijn aanwijzingen dat er geen significant sneller algoritme bestaat; een algoritme dat het tweedimensionale maximale subarrayprobleem oplost in O( n ^3−ε ) tijd, voor elke ε>0, zou een even snel algoritme impliceren voor het probleem met de kortste paden van alle paren .

Toepassingen

Maximale subarray-problemen doen zich op veel gebieden voor, zoals analyse van genomische sequenties en computervisie .

Genomische sequentieanalyse maakt gebruik van maximale subarray-algoritmen om belangrijke biologische segmenten van eiwitsequenties te identificeren. Deze problemen omvatten geconserveerde segmenten, GC-rijke regio's, tandemherhalingen, filter met lage complexiteit, DNA-bindende domeinen en regio's met een hoge lading.

In computer vision worden algoritmen met maximale subarray gebruikt op bitmapafbeeldingen om het helderste gebied in een afbeelding te detecteren.

Het algoritme van Kadane

Lege subarrays toegelaten

Voorbeeld run
Uitvoering van Kadane's algoritme op de bovenstaande voorbeeldarray. Blauw : subarray met de grootste som eindigend op i ; groen : subarray met de grootste som die tot nu toe is aangetroffen; een kleine letter geeft een lege array aan; variabele i wordt impliciet gelaten in Python-code.

Kadane's originele algoritme lost de probleemversie op wanneer lege subarrays worden toegelaten. Het scant de gegeven array van links naar rechts. In de e stap berekent het de subarray met de grootste som die eindigt op ; deze som wordt gehandhaafd in variabele . Bovendien berekent het de subarray met de grootste som ergens in , gehandhaafd in variabele , en gemakkelijk verkregen als het maximum van alle waarden tot nu toe gezien, vgl. regel 7 van het algoritme. ${\displaystyle A[1\ldots n]}$${\displaystyle j}$${\displaystyle j}$current_sum${\displaystyle A[1\ldots j]}$best_sumcurrent_sum

Als een lusinvariant , in de e stap, houdt de oude waarde van het maximum over de hele som . Daarom is het maximum over de hele som . Om dit laatste maximum uit te breiden om ook het geval te dekken , volstaat het om ook de lege subarray te beschouwen . Dit wordt gedaan in regel 6 door de nieuwe waarde van toe te wijzen , die daarna het maximum over de hele som bevat . ${\displaystyle j}$current_sum${\displaystyle i\in \{1,\ldots ,j\}}$${\displaystyle A[i]+\cdots +A[j-1]}$current_sum${\displaystyle +A[j]}$${\displaystyle i\in \{1,\ldots ,j\}}$${\displaystyle A[i]+\cdots +A[j]}$${\displaystyle i=j+1}$${\displaystyle A[j+1\;\ldots \;j]}$${\displaystyle \max(0,}$current_sum${\displaystyle +A[j])}$current_sum${\displaystyle i\in \{1,\ldots, j+1\}}$${\displaystyle A[i]+\cdots +A[j]}$

Het probleem kan dus worden opgelost met de volgende code, hier uitgedrukt in Python :

def max_subarray(numbers):
    """Find the largest sum of any contiguous subarray."""
    best_sum = 0  # or: float('-inf')
    current_sum = 0
    for x in numbers:
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

Deze versie van het algoritme retourneert 0 als de invoer geen positieve elementen bevat (ook als de invoer leeg is).

Geen lege subarrays toegelaten

Voor de variant van het probleem die lege subarrays niet toestaat, best_summoet in plaats daarvan worden geïnitialiseerd op negatief oneindig en ook in de for-lus current_summoet worden bijgewerkt als max(x, current_sum + x). In dat geval, als de invoer geen positief element bevat, is de geretourneerde waarde die van het grootste element (dwz de waarde die het dichtst bij 0 ligt), of negatief oneindig als de invoer leeg was.

De positie van de beste subarray berekenen

Het algoritme kan worden aangepast om ook de begin- en eindindexen van de maximale subarray bij te houden:

def max_subarray(numbers):
    """Find a contiguous subarray with the largest sum."""
    best_sum = 0  # or: float('-inf')
    best_start = best_end = 0  # or: None
    current_sum = 0
    for current_end, x in enumerate(numbers):
        if current_sum <= 0:
            # Start a new sequence at the current element
            current_start = current_end
            current_sum = x
        else:
            # Extend the existing sequence with the current element
            current_sum += x

        if current_sum > best_sum:
            best_sum = current_sum
            best_start = current_start
            best_end = current_end + 1  # the +1 is to make 'best_end' exclusive

    return best_sum, best_start, best_end

In Python worden arrays vanaf 0 geïndexeerd en wordt de eindindex meestal uitgesloten, zodat de subarray [22, 33] in de array [-11, 22, 33, -44] begint bij index 1 en eindigt bij index 3.

Complexiteit

Vanwege de manier waarop dit algoritme optimale substructuren gebruikt (de maximale subarray eindigend op elke positie wordt op een eenvoudige manier berekend uit een gerelateerd maar kleiner en overlappend subprobleem: de maximale subarray eindigend op de vorige positie) kan dit algoritme worden gezien als een eenvoudig/ triviaal voorbeeld van dynamisch programmeren .

De runtime-complexiteit van het algoritme van Kadane is . ${\ Displaystyle O (n)}$

generalisaties

Soortgelijke problemen kunnen worden gesteld voor hoger-dimensionale arrays, maar hun oplossingen zijn ingewikkelder; zie bijvoorbeeld Takaoka (2002) . Brodal & Jørgensen (2007) lieten zien hoe je de k grootste subarray-sommen in een eendimensionale array kunt vinden, in de optimale tijdsgebonden . ${\ Displaystyle O (n + k)}$

De maximale som k- disjuncte subarrays kunnen ook worden berekend in de optimale tijdsgrens . ${\ Displaystyle O (n + k)}$

Zie ook

• Subset som probleem

Opmerkingen:

Referenties

• Backurs, Arthur; Dikkala, Nishanth; Tzamos, Christos (2016), "Strakke hardheidsresultaten voor rechthoeken met maximaal gewicht", Proc. 43e internationaal colloquium over automaten, talen en programmeren : 81:1–81:13, doi : 10.4230/LIPIcs.ICALP.2016.81 , S2CID  1272136
• Bae, Sung Eun (2007), Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem (PDF) (Ph.D. thesis), University of Canterbury, S2CID  2681670 , gearchiveerd van het origineel (PDF) op 2017-10-26.
• Bengtsson, Fredrik; Chen, Jingsen (2007), Maximaal scorende segmenten optimaal berekenen (PDF) (Onderzoeksrapport), Luleå University of Technology
• Bentley, Jon (1984), "Programming Pearls: Algorithm Design Techniques", Mededelingen van de ACM , 27 (9): 865-873, doi : 10.1145/358234.381162 , S2CID  207565329
• Bentley, Jon (mei 1989), Programming Pearls (2e? ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1
• Bird, Richard S. (1989), "Algebraïsche identiteiten voor programmaberekening" (PDF) , The Computer Journal , 32 (2): 122-126, doi : 10.1093/comjnl/32.2.122
• Brodal, Gerth Stolting; Jørgensen, Allan Grønlund (2007), "Een lineair tijdalgoritme voor het k maximale sommen probleem", Mathematical Foundations of Computer Science , Lecture Notes in Computer Science, 4708 , Springer-Verlag, pp 442-453, doi : 10.1007/978 -3-540-74456-6_40.
• Gries, David (1982), "A Note on the Standard Strategy for Developing Loop Invariants and Loops" (PDF) , Science of Computer Programming , 2 (3): 207-241, doi : 10.1016/0167-6423 (83) 90015 -1 , hdl : 1813/6370
• Takaoka, Tadao (2002), "Efficiënte algoritmen voor het maximale subarrayprobleem door afstandsmatrixvermenigvuldiging", Electronic Notes in Theoretical Computer Science , 61 : 191-200, doi : 10.1016 / S1571-0661 (04) 00313-5.
• Tamaki, Hisao; Tokuyama, Takeshi (1998), "Algoritmen voor het maximale subarrayprobleem op basis van matrixvermenigvuldiging" , Proceedings of the 9th Symposium on Discrete Algorithms (SODA) : 446-452 , teruggewonnen 17 november 2018

Externe links

• TAN, Lirong. "Maximum aaneengesloten subarray Sum Problemen" (PDF) . Gearchiveerd van het origineel (PDF) op 10-10-2015 . Ontvangen 2017-10-26 .
• Mu, Shin-Cheng (2010). "The Maximum Segment Sum Probleem: de oorsprong, en een afleiding" .
• "Opmerkingen over het maximale subarray-probleem" . 2012.
• www.algorithmist.com
• alexeigor.wikidot.com
• grootste vervolgsomprobleem op Rosetta Code
• geeksforgeeks pagina op Kadane's Algorithm