Maksimalt subarray og maksimalt produkt-subarray
Anvend Kadane's algoritme på maximum-sum-subarray, og udvid den til at holde styr på både maksimum og minimum for produktvarianten.
Maksimalt subarray og maksimalt produkt-subarray er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Problemet med maksimal sum i et delarray
Problemet med maksimal sum i et delarray beder dig finde det sammenhængende delarray i et endimensionalt array af tal, der har den største sum. I [-2, 1, -3, 4, -1, 2, 1, -5, 4] giver delarrayet [4, -1, 2, 1] for eksempel den maksimale sum på 6. En udtømmende tilgang med O(n²) gennemgår alle delarrays, men Kadane's 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) # 6Intuition bag Kadane's algoritme
Kadane's algoritme gennemløber arrayet én gang og vedligeholder en løbende current_sum. Ved hvert element skal du afgøre, om det er bedre at udvide det eksisterende delarray eller starte forfra med dette element. Hvis current_sum bliver negativ, vil det kun skade fremtidige delarrays, så start forfra. Gentagelsesrelationen 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)) # 6Gennemgang af Kadane's algoritme
Lad os gennemgå Kadane's 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 identificerer korrekt delarrayet, der slutter ved indeks 6, som det 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])Returnering af det faktiske delarray
Hvis intervieweren beder dig om at returnere selve delarrayet og ikke kun summen, skal du følge start- og slutindekserne. Når du starter forfra, fordi num > current_sum + num, skal du opdatere en temp_start. Når du opdaterer max_sum, skal du gemme temp_start som start og det aktuelle indeks som end. Det giver O(1) ekstra pladsforbrug i den samme O(n)-algoritme.
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])Problemet med maksimalt produkt i et delarray
Problemet med maksimalt produkt i et delarray er vanskeligere end sumvarianten på grund af negative tal. To negative tal giver et positivt produkt, så et meget negativt produkt kan blive det maksimale, når det multipliceres med endnu et negativt tal. For [2, 3, -2, 4] er svaret 6 ([2, 3]). For [-2, 0, -1] er svaret 0. Vi skal følge både maksimale og minimale produkter ved hvert trin.
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)Sporing af både maksimale og minimale produkter
Den afgørende indsigt er, at det aktuelle maksimale produkt ved hver position er enten num, max_so_far * num eller min_so_far * num. Den sidste mulighed er nyttig, når et negativt tal vender minimum til maksimum. Det samme gælder for minimum. Opdater begge cur_max og cur_min samtidig ved hjælp af de tidligere værdier, så du undgår at bruge værdier, der allerede er blevet opdateret i det samme trin.
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 vigtig
Betragt [-3, -10, 5]. Efter behandling af -3: max=-3, min=-3. Efter -10: kandidaterne er (-10, 30, 30) → max=30, min=-10. Efter 5: kandidaterne er (5, 150, -50) → max=150. Hvis du ikke følger min_prod, overser du det skift, der opstår, når et meget negativt minimum multipliceres med endnu et negativt tal. Beregn altid både max og min ud fra de samme tidligere værdier for at undgå en fejl med læsning af forældede værdier.
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 nulstiller produktet
Et nul i arrayet nulstiller begge løbende produkter og opdeler dermed arrayet i uafhængige delarrays. Når num = 0, er både max_prod * 0 = 0 og min_prod * 0 = 0, så alle tre kandidater bliver 0, og maksimumsværdien fra det tidligere resultat bevares. Der er ikke brug for særskilt kode — den generelle formel håndterer nuller naturligt.
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: produktgennemløb fra venstre mod højre
En alternativ tilgang gennemløber fra venstre mod højre og fra højre mod venstre og nulstiller det løbende produkt til 1, når det møder et nul. Det maksimale produktdelarray krydser aldrig et nul, så hvis et negativt tal gør resultatet dårligt i den ene retning, opfanger det omvendte gennemløb skiftet. Denne tilgang er elegant, men metoden med sporing af minimum og maksimum forventes oftere til jobsamtaler.
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])) # 0Kadane's algoritme kontra produkt: vigtige forskelle
Sum- og produktdelarrays adskiller sig på vigtige måder. For summer er negative tal altid skadelige, så du starter grådigt forfra. For produkter hjælper to negative tal, så du skal følge begge yderpunkter. Desuden er nuller afsluttende for produkter, men kun moderat skadelige for summer. Når du forklarer løsningen til en jobsamtale, skal du udtrykkeligt anerkende disse forskelle og forklare, hvorfor det er nødvendigt at følge minimum, før du 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 tips til jobsamtalen
Både Kadane's algoritme (maksimal sum) og metoden med sporing af minimum og maksimum (maksimalt produkt) bruger O(n)-tid og O(1)-plads. Vigtige tips til jobsamtalen: (1) Nævn del-og-hersk-alternativet med O(n log n) for maksimal sum for at vise bredden i din viden. (2) Understreg for maksimalt produkt, at du opdaterer min_prod og max_prod samtidig ud fra tidligere værdier, så du undgår at bruge forældede data. (3) Afklar altid: Kan arrayet være tomt? Skal delarrayet være ikke-tomt? Ja, det skal være ikke-tomt efter konventionen.
# 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 negativeHurtig test
Test din forståelse af begreberne fra denne lektion i Data Structures & Algorithms — Coding Interview Prep.
Opsummering af lektionen
I denne lektion lærte du: Kadane's algoritme løser problemet med maksimal sum i et delarray på O(n) ved at vælge, om hvert element skal føjes til det eksisterende delarray, eller om der skal startes forfra, problemet med maksimalt produkt i et delarray kræver, at både de minimale og maksimale løbende produkter følges, fordi negative tal kan vende resultatet, og nuller nulstiller det løbende produkt naturligt uden særskilt kode. Næste emne er problemet med orddeling ved hjælp af en 1D-DP-tabel.
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Maksimalt subarray og maksimalt produkt-subarray” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Maksimalt subarray og maksimalt produkt-subarray”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Maksimalt subarray og maksimalt produkt-subarray”?
Anvend Kadane's algoritme på maximum-sum-subarray, og udvid den til at holde styr på både maksimum og minimum for produktvarianten. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.
Hvor lang tid tager lektionen “Maksimalt subarray og maksimalt produkt-subarray”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- House Robber: tag-eller-spring-over-rekurrens
- Maksimalt subarray og maksimalt produkt-subarray
- Word Break og segmentering af strenge
- Decode Ways og optælling af stier