Delarray med maximal summa och maximal produkt
Tillämpa Kadane-algoritmen på maximum-sum-subarray och utöka den genom att hålla reda på både maximum och minimum för produktvarianten.
Delarray med maximal summa och maximal produkt är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 2 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Problemet med delarrayen med maximal summa
Problemet Maximum Subarray går ut på att hitta den sammanhängande delarrayen i en endimensionell array med tal som har störst summa. I [-2, 1, -3, 4, -1, 2, 1, -5, 4] ger till exempel delarrayen [4, -1, 2, 1] den maximala summan 6. En brute-force-metod med O(n²) kontrollerar alla delarrayer, men Kadane's algorithm löser problemet i 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) # 6Intuitionen bakom Kadane's algorithm
Kadane's algorithm går igenom arrayen i ett enda varv och håller reda på en löpande current_sum. Vid varje element avgör ni om det är bättre att förlänga den befintliga delarrayen eller börja om från det här elementet. Om current_sum blir negativt skulle det bara försämra alla framtida delarrayer, så ni börjar om. Rekurrensen är 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)) # 6Följ Kadane's algorithm steg för steg
Låt oss följa Kadane's algorithm på [-2, 1, -3, 4, -1, 2, 1, -5, 4]: börja med curr=-2, max=-2. Vid 1: curr=max(1,-2+1)=1, max=1. Vid -3: curr=max(-3,1-3)=-2, max=1. Vid 4: curr=max(4,-2+4)=4, max=4. Vid -1: curr=3, max=4. Vid 2: curr=5, max=5. Vid 1: curr=6, max=6. Vid -5: curr=1. Vid 4: curr=5, max=6. Algoritmen identifierar korrekt delarrayen som slutar vid index 6 som den optimala.
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])Returnera den faktiska delarrayen
Om intervjuaren ber er att returnera själva delarrayen (inte bara summan) måste ni hålla reda på start- och slutindex. När ni börjar om (eftersom num > current_sum + num) uppdaterar ni temp_start. När ni uppdaterar max_sum sparar ni temp_start som start och det aktuella indexet som end. Detta ger O(1) extra utrymmesåtgång i samma O(n)-algoritm.
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 delarrayen med maximal produkt
Problemet Maximum Product Subarray är mer komplicerat än summavarianten på grund av negativa tal. Två negativa tal ger en positiv produkt, så en mycket negativ produkt kan bli den maximala efter multiplikation med ytterligare ett negativt tal. För [2, 3, -2, 4] är svaret 6 ([2, 3]). För [-2, 0, -1] är svaret 0. Vi måste hålla reda på både maximala och minimala produkter i varje steg.
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)Håll reda på både maximala och minimala produkter
Den viktiga insikten är att den aktuella maximala produkten vid varje position är en av num, max_so_far * num eller min_so_far * num (den sista hjälper när ett negativt tal vänder minimum till maximum). På motsvarande sätt gäller detta för minimum. Uppdatera både cur_max och cur_min samtidigt med hjälp av de tidigare värdena, så att ni undviker att använda redan uppdaterade värden i samma steg.
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])) # -2Varför min_prod är viktigt
Betrakta [-3, -10, 5]. Efter behandling av -3: max=-3, min=-3. Efter -10: kandidaterna är (-10, 30, 30) → max=30, min=-10. Efter 5: kandidaterna är (5, 150, -50) → max=150. Utan att hålla reda på min_prod skulle ni missa vändningen som sker när ett kraftigt negativt minimum multipliceras med ytterligare ett negativt tal. Beräkna alltid både max och min från samma tidigare värden för att undvika ett fel med inaktuella värden.
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: 150Nollor återställer produkten
En nolla i arrayen återställer båda de löpande produkterna till noll och delar därmed effektivt upp arrayen i oberoende delarrayer. När num = 0 gäller både max_prod * 0 = 0 och min_prod * 0 = 0, så alla tre kandidater blir 0 och maximum från det tidigare resultatet bevaras. Ingen specialhantering behövs — den generella formeln hanterar nollor 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: svep från vänster och höger
En alternativ metod går från vänster till höger och från höger till vänster och återställer den löpande produkten till 1 när den stöter på noll. Delarrayen med maximal produkt går aldrig över en nolla, så om ett negativt tal försämrar resultatet i ena riktningen fångar det omvända svepet upp vändningen. Metoden är elegant, men min/max-spårning är det som oftare förväntas på 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])) # 0Kadane jämfört med produkt: viktiga skillnader
Delarrayer för summor och produkter skiljer sig åt på viktiga sätt. För summor är negativa tal alltid skadliga, så ni börjar om direkt. För produkter kan två negativa tal vara gynnsamma, så ni måste hålla reda på båda ytterligheterna. Dessutom avslutar nollor produktsekvenser, medan de bara är måttligt skadliga för summor. När ni förklarar lösningen på intervjuer bör ni uttryckligen påpeka dessa skillnader och förklara varför det är nödvändigt att hålla reda på minimum innan ni skriver kod.
# 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])) # 24Komplexitet och intervjutips
Både Kadane's algorithm (maximal summa) och min/max-spårning (maximal produkt) körs på O(n) tid och använder O(1) utrymme. Viktiga intervjutips: (1) För maximal summa kan ni nämna Divide and Conquer-alternativet med O(n log n) för att visa bredd. (2) För maximal produkt bör ni betona att ni uppdaterar min_prod och max_prod samtidigt utifrån tidigare värden, så att ni undviker att använda inaktuella data. (3) Klargör alltid: kan arrayen vara tom? Måste delarrayen vara icke-tom? (Ja, enligt konvention måste den vara icke-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 negativeSnabbtest
Testa er förståelse av begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionens sammanfattning
I den här lektionen lärde ni er: Kadane's algorithm löser problemet med delarrayen med maximal summa i O(n) genom att välja om den ska förlängas eller startas om vid varje element, problemet med delarrayen med maximal produkt kräver att både minimala och maximala löpande produkter spåras eftersom negativa tal kan vända tecken och nollor återställer den löpande produkten naturligt utan specialhantering. Härnäst utforskar vi problemet Word Break med hjälp av en endimensionell DP-tabell.
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Delarray med maximal summa och maximal produkt” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Delarray med maximal summa och maximal produkt”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”Delarray med maximal summa och maximal produkt”?
Tillämpa Kadane-algoritmen på maximum-sum-subarray och utöka den genom att hålla reda på både maximum och minimum för produktvarianten. Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 2 av 4.
Hur lång tid tar lektionen ”Delarray med maximal summa och maximal produkt”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- House Robber: rekurrens för ta eller hoppa över
- Delarray med maximal summa och maximal produkt
- Word Break och segmentering av strängar
- Decode Ways och räkning av vägar