Suurin alitaulukkosumma ja suurin tulon alitaulukko
Soveltakaa Kadane-algoritmia suurimman summan alitaulukkoon ja laajentakaa sitä seuraamaan sekä maksimi- että minimiarvoa tulomuunnelmaa varten.
Suurin alitaulukkosumma ja suurin tulon alitaulukko on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Maximum Subarray -ongelma
Maximum Subarray -ongelmassa on löydettävä yksiulotteisesta lukutaulukosta peräkkäinen osataulukko, jonka summa on suurin. Esimerkiksi taulukossa [-2, 1, -3, 4, -1, 2, 1, -5, 4] osataulukko [4, -1, 2, 1] tuottaa suurimman summan 6. Raakavoimainen O(n²)-lähestymistapa käy läpi kaikki osataulukot, mutta Kadane's algorithm ratkaisee ongelman ajassa 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) # 6Kadane's algorithmin periaate
Kadane's algorithm käy taulukon läpi kerran ja ylläpitää juoksevaa current_sum-summaa. Jokaisen alkion kohdalla on päätettävä: onko parempi jatkaa olemassa olevaa osataulukkoa vai aloittaa uusi tästä alkiosta? Jos current_sum muuttuu negatiiviseksi, se vain heikentäisi kaikkia tulevia osataulukoita, joten aloitetaan alusta. Rekurrenssi on 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)) # 6Kadane's algorithmin vaiheittainen seuranta
Seurataan Kadane's algorithm -algoritmia taulukossa [-2, 1, -3, 4, -1, 2, 1, -5, 4]: aloitetaan arvoilla curr=-2, max=-2. Arvolla 1: curr=max(1,-2+1)=1, max=1. Arvolla -3: curr=max(-3,1-3)=-2, max=1. Arvolla 4: curr=max(4,-2+4)=4, max=4. Arvolla -1: curr=3, max=4. Arvolla 2: curr=5, max=5. Arvolla 1: curr=6, max=6. Arvolla -5: curr=1. Arvolla 4: curr=5, max=6. Algoritmi tunnistaa oikein indeksistä 6 päättyvän osataulukon parhaaksi.
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])Todellisen osataulukon palauttaminen
Jos haastattelija pyytää palauttamaan itse osataulukon eikä pelkästään summaa, sinun on seurattava alku- ja loppuindeksejä. Kun aloitat alusta (koska num > current_sum + num), päivitä temp_start. Kun päivität max_sum-arvon, tallenna temp_start arvoksi start ja nykyinen indeksi arvoksi end. Tämä lisää samaan O(n)-algoritmiin vain O(1)-lisätilan.
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])Maximum Product Subarray -ongelma
Maximum Product Subarray -ongelma on summa-versiota hankalampi negatiivisten lukujen vuoksi. Kaksi negatiivista lukua tuottaa kertolaskussa positiivisen tuloksen, joten hyvin negatiivinen tulo voi muuttua suurimmaksi tuloksi, kun se kerrotaan toisella negatiivisella luvulla. Taulukossa [2, 3, -2, 4] vastaus on 6 ([2, 3]). Taulukossa [-2, 0, -1] vastaus on 0. Jokaisessa vaiheessa on seurattava sekä suurinta että pienintä tuloa.
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)Suurimman ja pienimmän tulon seuranta
Keskeinen oivallus on tämä: jokaisessa kohdassa nykyinen suurin tulo on jokin arvoista num, max_so_far * num tai min_so_far * num (viimeinen vaihtoehto auttaa, kun negatiivinen luku muuttaa pienimmän tulon suurimmaksi). Sama pätee pienimpään tuloon. Päivitä molemmat arvot cur_max ja cur_min samanaikaisesti aiempien arvojen perusteella, jotta et käytä samassa vaiheessa jo päivitettyjä arvoja.
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])) # -2Miksi min_prod on tärkeä
Tarkastellaan taulukkoa [-3, -10, 5]. Kun -3 on käsitelty: max=-3, min=-3. Kun -10 on käsitelty: ehdokkaat ovat (-10, 30, 30) → max=30, min=-10. Kun 5 on käsitelty: ehdokkaat ovat (5, 150, -50) → max=150. Jos et seuraa arvoa min_prod, et huomaisi muutosta, joka tapahtuu, kun hyvin negatiivinen minimi kerrotaan toisella negatiivisella luvulla. Laske aina sekä max että min samoista aiemmista arvoista, jotta vältät vanhentuneen arvon lukemiseen liittyvän virheen.
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: 150Nollat nollaavat tulon
Taulukossa oleva nolla nollaa molemmat juoksevat tulot ja jakaa taulukon käytännössä toisistaan riippumattomiin osataulukoihin. Kun num = 0, sekä max_prod * 0 = 0 että min_prod * 0 = 0, joten kaikki kolme ehdokasta ovat 0 ja aiempi maksimitulos säilyy. Erityiskäsittelyä ei tarvita — yleinen kaava käsittelee nollat luonnostaan.
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])) # 0Vaihtoehto: tulojen läpikäynti vasemmalta oikealle ja oikealta vasemmalle
Vaihtoehtoisessa lähestymistavassa taulukko käydään läpi vasemmalta oikealle ja oikealta vasemmalle, ja juokseva tulo palautetaan arvoon 1, kun vastaan tulee nolla. Suurimman tulon osataulukko ei koskaan ylitä nollaa, joten jos negatiivinen luku heikentää tulosta toisessa suunnassa, käänteinen läpikäynti havaitsee muutoksen. Tämä lähestymistapa on elegantti, mutta min/max-seurantamenetelmää odotetaan haastatteluissa yleensä useammin.
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 algorithm ja tulot: keskeiset erot
Summa- ja tulo-osataulukot eroavat toisistaan tärkeillä tavoilla. Summissa negatiiviset luvut ovat aina haitallisia, joten aloitus tehdään ahneesti uudelleen. Tuloissa kaksi negatiivista lukua auttaa, joten on seurattava molempia ääripäitä. Lisäksi nollat päättävät tulon laskennan, kun taas summiin ne vaikuttavat vain vähän. Haastattelussa nämä erot kannattaa tuoda selvästi esiin ja selittää, miksi myös min-arvoa on seurattava, ennen kuin kirjoitat koodia.
# 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])) # 24Aikavaativuus ja haastatteluvinkit
Sekä Kadane's algorithm (maksimisumma) että min/max-seuranta (maksimitulo) toimivat ajassa O(n) ja tilassa O(1). Keskeiset haastatteluvinkit: (1) Mainitse maksimisummaa varten Divide and Conquer -vaihtoehto, jonka aikavaativuus on O(n log n), osoittaaksesi osaamisesi laajuuden. (2) Korosta maksimituloa varten, että päivität min_prod- ja max_prod-arvot samanaikaisesti aiempien arvojen perusteella, jotta et käytä vanhentuneita tietoja. (3) Selvitä aina: voiko taulukko olla tyhjä? Onko osataulukon oltava epätyhjä? (Kyllä, käytännön oletuksena sen on oltava epätyhjä.)
# 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 negativePikatarkistus
Testaa, miten hyvin hallitset tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteet.
Oppitunnin kertaus
Tässä oppitunnissa opit: Kadane's algorithm ratkaisee suurimman summan osataulukon ongelman ajassa O(n) valitsemalla jokaisen alkion kohdalla jatkamisen tai uudelleen aloittamisen, Maximum Product Subarray edellyttää sekä pienimpien että suurimpien juoksevien tulojen seuraamista negatiivisten lukujen aiheuttamien muutosten vuoksi ja nollat nollaavat juoksevan tulon luonnollisesti ilman erityiskäsittelyä. Seuraavaksi tarkastelemme Word Break -ongelmaa yksiulotteisen DP-taulukon avulla.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Suurin alitaulukkosumma ja suurin tulon alitaulukko” ilmainen?
Kyllä – oppitunnin ”Suurin alitaulukkosumma ja suurin tulon alitaulukko” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Suurin alitaulukkosumma ja suurin tulon alitaulukko”?
Soveltakaa Kadane-algoritmia suurimman summan alitaulukkoon ja laajentakaa sitä seuraamaan sekä maksimi- että minimiarvoa tulomuunnelmaa varten. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”Suurin alitaulukkosumma ja suurin tulon alitaulukko”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- House Robber: ota tai ohita -rekurrenssi
- Suurin alitaulukkosumma ja suurin tulon alitaulukko
- Word Break ja merkkijonon pilkkominen
- Decode Ways ja polkujen laskeminen