Maksimumsdelarray og maksimumsproduktdelarray
Bruk Kadane's algorithm på maximum-sum-subarray, og utvid den til å holde oversikt over både maksimum og minimum for produktvarianten.
Maksimumsdelarray og maksimumsproduktdelarray er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Problem med delarray med maksimal sum
Problemet Maximum Subarray går ut på å finne den sammenhengende delarrayen i en endimensjonal array med tall som har størst sum. I [-2, 1, -3, 4, -1, 2, 1, -5, 4] gir for eksempel delarrayen [4, -1, 2, 1] den maksimale summen 6. En brute force-tilnærming med O(n²) går gjennom alle delarrayer, men Kadanes algoritme løser problemet på O(n).
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Brute force: O(n^2)
max_sum = float('-inf')
for i in range(len(nums)):
curr = 0
for j in range(i, len(nums)):
curr += nums[j]
max_sum = max(max_sum, curr)
print(max_sum) # 6Intuisjonen bak Kadanes algoritme
Kadanes algoritme går gjennom arrayen én gang og opprettholder en løpende sum i current_sum. For hvert element avgjør De om det er best å utvide den eksisterende delarrayen eller starte på nytt med dette elementet. Hvis current_sum blir negativ, vil den bare svekke enhver fremtidig delarray, så algoritmen starter på nytt. Rekurrensen er current_sum = max(num, current_sum + num).
def max_subarray(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
# Extend or start fresh?
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(nums)) # 6Sporing av Kadanes algoritme
La oss følge Kadanes algoritme på [-2, 1, -3, 4, -1, 2, 1, -5, 4]: start med curr=-2, max=-2. Ved 1: curr=max(1,-2+1)=1, max=1. Ved -3: curr=max(-3,1-3)=-2, max=1. Ved 4: curr=max(4,-2+4)=4, max=4. Ved -1: curr=3, max=4. Ved 2: curr=5, max=5. Ved 1: curr=6, max=6. Ved -5: curr=1. Ved 4: curr=5, max=6. Algoritmen identifiserer korrekt delarrayen som slutter på indeks 6 som den optimale.
def max_subarray_trace(nums):
curr = max_sum = nums[0]
for i, num in enumerate(nums[1:], 1):
new_curr = max(num, curr + num)
max_sum = max(max_sum, new_curr)
print(f'i={i}, num={num}, curr: {curr}->{new_curr}, max={max_sum}')
curr = new_curr
return max_sum
max_subarray_trace([-2, 1, -3, 4, -1, 2, 1, -5, 4])Returnere den faktiske delarrayen
Hvis intervjueren ber Dem om å returnere selve delarrayen (ikke bare summen), må De holde oversikt over start- og sluttindeksene. Når De starter på nytt (fordi num > current_sum + num), oppdaterer De en temp_start. Når De oppdaterer max_sum, lagrer De temp_start som start og den gjeldende indeksen som end. Dette gir O(1) ekstra minnebruk i den samme O(n)-algoritmen.
def max_subarray_indices(nums):
max_sum = curr = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if nums[i] > curr + nums[i]:
curr = nums[i]
temp_start = i
else:
curr += nums[i]
if curr > max_sum:
max_sum = curr
start, end = temp_start, i
return max_sum, nums[start:end+1]
print(max_subarray_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# (6, [4, -1, 2, 1])Problem med delarray med maksimalt produkt
Problemet Maximum Product Subarray er mer utfordrende enn sumvarianten på grunn av negative tall. To negative tall gir et positivt produkt, så et svært negativt produkt kan bli det maksimale etter multiplikasjon med et annet negativt tall. For [2, 3, -2, 4] er svaret 6 ([2, 3]). For [-2, 0, -1] er svaret 0. Vi må holde oversikt over både maksimale og minimale produkter ved hvert trinn.
nums = [2, 3, -2, 4]
# [2,3,-2,4]: products [2, 6, -12, -48]
# subarrays: [2]=2, [2,3]=6, [3]=3, etc.
# max is 6 from subarray [2,3]
nums2 = [-2, 3, -4]
# [-2]*3*[-4] = 24
# negative*negative=positive!
print('Expected:', 24)Holde oversikt over både maksimale og minimale produkter
Den viktigste innsikten er at det gjeldende maksimale produktet ved hver posisjon er ett av num, max_so_far * num eller min_so_far * num (det siste er nyttig når et negativt tall snur minimum til maksimum). Det samme gjelder for minimumet. Oppdater både cur_max og cur_min samtidig ved hjelp av de tidligere verdiene, slik at De unngår å bruke allerede oppdaterte verdier i samme trinn.
def max_product(nums):
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
# All three candidates for new max
candidates = (num, max_prod * num, min_prod * num)
max_prod, min_prod = max(candidates), min(candidates)
result = max(result, max_prod)
return result
print(max_product([2, 3, -2, 4])) # 6
print(max_product([-2, 3, -4])) # 24
print(max_product([-2, 0, -1])) # 0
print(max_product([-2])) # -2Hvorfor min_prod er viktig
Se på [-3, -10, 5]. Etter behandling av -3: max=-3, min=-3. Etter -10: kandidatene er (-10, 30, 30) → max=30, min=-10. Etter 5: kandidatene er (5, 150, -50) → max=150. Uten å holde oversikt over min_prod ville De gått glipp av vendingen som skjer når et stort negativt minimum multipliseres med et annet negativt tall. Beregn alltid både max og min ut fra de samme tidligere verdiene for å unngå en feil med foreldede verdier.
def max_product_traced(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
prev_max, prev_min = max_p, min_p
max_p = max(num, prev_max * num, prev_min * num)
min_p = min(num, prev_max * num, prev_min * num)
result = max(result, max_p)
print(f'num={num}: max_p={max_p}, min_p={min_p}')
return result
max_product_traced([-3, -10, 5])
# max_p after -10: 30 (flip!)
# max_p after 5: 150Nuller nullstiller produktet
Et null i arrayen nullstiller begge løpende produkter, slik at arrayen i praksis deles opp i uavhengige delarrayer. Når num = 0, blir både max_prod * 0 = 0 og min_prod * 0 = 0, så alle tre kandidatene blir 0, mens maksimumet fra det tidligere resultatet beholdes. Det er ikke nødvendig med spesialkode — den generelle formelen håndterer nuller naturlig.
def max_product(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
cands = (num, max_p * num, min_p * num)
max_p, min_p = max(cands), min(cands)
result = max(result, max_p)
return result
# Zero splits array into independent subarrays
print(max_product([3, -1, 4, 0, 2, 5, -1])) # 10 (2*5)
print(max_product([0, 2])) # 2
print(max_product([-1, 0, -2])) # 0Alternativ: produkt-sveip fra venstre og høyre
En alternativ tilnærming går fra venstre mot høyre og fra høyre mot venstre, og nullstiller det løpende produktet til 1 når det møter et null. Den maksimale delarrayen kan aldri krysse et null, så hvis et negativt tall gir et dårlig resultat i én retning, vil det omvendte sveipet fange opp vendingen. Denne tilnærmingen er elegant, men metoden med sporing av minimum og maksimum forventes oftere i intervjuer.
def max_product_sweep(nums):
result = max(nums)
left = right = 1
n = len(nums)
for i in range(n):
left *= nums[i]
right *= nums[n - 1 - i]
result = max(result, left, right)
if left == 0: left = 1
if right == 0: right = 1
return result
print(max_product_sweep([2, 3, -2, 4])) # 6
print(max_product_sweep([-2, 3, -4])) # 24
print(max_product_sweep([-2, 0, -1])) # 0Kadanes algoritme kontra produkt: viktige forskjeller
Delarrayer for sum og produkt skiller seg fra hverandre på viktige måter. For sum er negative tall alltid skadelige, så De starter grådig på nytt. For produkt kan to negative tall være fordelaktige, så De må holde oversikt over begge ytterpunktene. I tillegg er nuller avsluttende for produkter, mens de bare er litt skadelige for summer. Når De forklarer dette i et intervju, bør De tydelig påpeke forskjellene og forklare hvorfor det er nødvendig å holde oversikt over min før De skriver kode.
# Max Sum Subarray: O(n) time, O(1) space
def max_sum(nums):
curr = result = nums[0]
for n in nums[1:]:
curr = max(n, curr + n) # restart or extend
result = max(result, curr)
return result
# Max Product Subarray: O(n) time, O(1) space
def max_prod(nums):
lo = hi = result = nums[0]
for n in nums[1:]:
lo, hi = min(n, lo*n, hi*n), max(n, lo*n, hi*n)
result = max(result, hi)
return result
print(max_sum([-2, 1, -3, 4, -1, 2, 1])) # 6
print(max_prod([-2, 3, -4])) # 24Kompleksitet og intervjutips
Både Kadanes algoritme (maksimal sum) og sporing av minimum/maksimum (maksimalt produkt) bruker O(n) tid og O(1) minne. Viktige intervjutips: (1) For maksimal sum kan De nevne del-og-hersk-alternativet med O(n log n) for å vise bredde. (2) For maksimalt produkt bør De fremheve at min_prod og max_prod oppdateres samtidig ut fra tidligere verdier, slik at De unngår å bruke foreldede data. (3) Avklar alltid: Kan arrayen være tom? Må delarrayen være ikke-tom? (Ja, etter konvensjonen må den være ikke-tom.)
# Both run O(n) time, O(1) space
# Kadane handles: all negative (returns least negative)
# Product handles: zeros (resets naturally), negatives (tracks both extremes)
nums_all_neg = [-5, -2, -8]
print('Max sum (all neg):', max(max(nums_all_neg[0:1]),
max(x for x in nums_all_neg))) # -2
# Correct: return the maximum element when all are negativeHurtigsjekk
Test forståelsen Deres av konseptene Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte De: Kadanes algoritme løser problemet med delarray med maksimal sum på O(n) ved å velge mellom å utvide eller starte på nytt ved hvert element, problemet med delarray med maksimalt produkt krever sporing av både minimale og maksimale løpende produkter på grunn av vendinger forårsaket av negative tall, og nuller nullstiller det løpende produktet naturlig uten spesialkode. Deretter skal vi se nærmere på problemet Word Break ved hjelp av en 1D-DP-tabell.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Maksimumsdelarray og maksimumsproduktdelarray» gratis?
Ja – hele teksten i «Maksimumsdelarray og maksimumsproduktdelarray» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Maksimumsdelarray og maksimumsproduktdelarray»?
Bruk Kadane's algorithm på maximum-sum-subarray, og utvid den til å holde oversikt over både maksimum og minimum for produktvarianten. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «Maksimumsdelarray og maksimumsproduktdelarray»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- House Robber: ta-eller-hopp over-rekurrens
- Maksimumsdelarray og maksimumsproduktdelarray
- Word Break og segmentering av strenger
- Decode Ways og telling av stier