Maximumsubarray en maximumproductsubarray

Het probleem van de maximale deelarray vraagt je om de aaneengesloten deelarray binnen een eendimensionale array met getallen te vinden die de grootste som heeft. In [-2, 1, -3, 4, -1, 2, 1, -5, 4] levert de deelarray [4, -1, 2, 1] bijvoorbeeld de maximale som van 6 op. Een brute-forcebenadering in O(n²) controleert alle deelarrays, maar het algoritme van Kadane lost dit op in O(n).

Het algoritme van Kadane doorloopt de array één keer en houdt een lopende current_sum bij. Bij elk element bepaal je wat beter is: de bestaande deelarray uitbreiden of opnieuw beginnen met dit element? Als current_sum negatief wordt, zou dat elke toekomstige deelarray alleen maar schaden, dus begin je opnieuw. De recurrentie is current_sum = max(num, current_sum + num).

Laten we Kadane stap voor stap volgen op [-2, 1, -3, 4, -1, 2, 1, -5, 4]: begin met curr=-2, max=-2. Bij 1: curr=max(1,-2+1)=1, max=1. Bij -3: curr=max(-3,1-3)=-2, max=1. Bij 4: curr=max(4,-2+4)=4, max=4. Bij -1: curr=3, max=4. Bij 2: curr=5, max=5. Bij 1: curr=6, max=6. Bij -5: curr=1. Bij 4: curr=5, max=6. Het algoritme identificeert correct de deelarray die eindigt op index 6 als de optimale deelarray.

Als de interviewer je vraagt om de deelarray zelf terug te geven en niet alleen de som, moet je de begin- en eindindex bijhouden. Wanneer je opnieuw begint omdat num > current_sum + num, werk je een temp_start bij. Wanneer je max_sum bijwerkt, sla je temp_start op als start en de huidige index als end. Dit voegt O(1) overhead toe aan hetzelfde O(n)-algoritme.

Het probleem van de deelarray met maximaal product is lastiger dan de variant met som vanwege negatieve getallen. Twee negatieve getallen leveren bij vermenigvuldiging een positief getal op, dus een zeer negatief product kan het maximum worden nadat het met nog een negatief getal is vermenigvuldigd. Voor [2, 3, -2, 4] is het antwoord 6 ([2, 3]). Voor [-2, 0, -1] is het antwoord 0. We moeten bij elke stap zowel de maximale als minimale producten bijhouden.

Het belangrijkste inzicht: op elke positie is het huidige maximale product een van num, max_so_far * num of min_so_far * num. Die laatste mogelijkheid is nuttig wanneer een negatief getal het minimum in een maximum omkeert. Hetzelfde geldt voor het minimum. Werk beide cur_max en cur_min gelijktijdig bij met de vorige waarden, zodat je in dezelfde stap geen al bijgewerkte waarden gebruikt.

Neem [-3, -10, 5]. Na het verwerken van -3: max=-3, min=-3. Na -10: de kandidaten zijn (-10, 30, 30) → max=30, min=-10. Na 5: de kandidaten zijn (5, 150, -50) → max=150. Zonder min_prod bij te houden, zou je de omkering missen die optreedt wanneer een sterk negatief minimum met nog een negatief getal wordt vermenigvuldigd. Bereken altijd zowel max als min op basis van dezelfde vorige waarden om een bug door het lezen van verouderde waarden te voorkomen.

Een nul in de array zet beide lopende producten terug op nul en splitst de array daardoor effectief op in onafhankelijke deelarrays. Wanneer num = 0, geldt zowel max_prod * 0 = 0 als min_prod * 0 = 0. Alle drie de kandidaten worden dus 0 en het vorige resultaat voor het maximum blijft behouden. Er is geen speciale code nodig — de algemene formule verwerkt nullen vanzelf.

Een alternatieve aanpak doorloopt de array van links naar rechts en van rechts naar links en zet het lopende product terug op 1 wanneer het een nul tegenkomt. De deelarray met maximaal product loopt nooit over een nul heen. Als een negatief getal de situatie in één richting verslechtert, vangt de omgekeerde scan de omkering op. Deze aanpak is elegant, maar de methode waarbij je het minimum en maximum bijhoudt wordt tijdens sollicitatiegesprekken vaker verwacht.

Deelarrays met een som en deelarrays met een product verschillen op belangrijke punten. Bij een som zijn negatieve getallen altijd schadelijk, dus begin je hebzuchtig opnieuw. Bij een product helpen twee negatieve getallen, dus moet je beide uitersten bijhouden. Bovendien beëindigen nullen productberekeningen, terwijl ze voor sommen slechts beperkt schadelijk zijn. Benoem deze verschillen tijdens een sollicitatiegesprek expliciet en leg uit waarom het nodig is om het minimum bij te houden voordat je code schrijft.

Zowel het algoritme van Kadane voor de maximale som als het bijhouden van minimum en maximum voor het maximale product werkt in O(n)-tijd en gebruikt O(1) ruimte. Belangrijke tips voor sollicitatiegesprekken: (1) Noem bij de maximale som het verdeel-en-heersalternatief in O(n log n) om je brede kennis te laten zien. (2) Benadruk bij het maximale product dat je min_prod en max_prod gelijktijdig bijwerkt op basis van vorige waarden, zodat je geen verouderde gegevens gebruikt. (3) Verduidelijk altijd: mag de array leeg zijn? Moet de deelarray niet-leeg zijn? (Ja, volgens de conventie moet die niet-leeg zijn.)

In deze les heb je geleerd: het algoritme van Kadane lost de deelarray met maximale som op in O(n) door bij elk element te kiezen tussen uitbreiden en opnieuw beginnen, voor de deelarray met maximaal product moet je zowel de minimale als maximale lopende producten bijhouden vanwege omkeringen door negatieve getallen en nullen zetten het lopende product vanzelf terug zonder speciale code. Vervolgens bekijken we het probleem van de woordafbreking met een eendimensionale dp-tabel.