Maksymalna podtablica i podtablica o maksymalnym iloczynie
Zastosują Państwo algorytm Kadane’a do zadania maximum-sum-subarray i rozszerzą go tak, aby śledzić jednocześnie maksimum i minimum w wariancie iloczynowym.
Maksymalna podtablica i podtablica o maksymalnym iloczynie to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Problem największej sumy podtablicy
Problem Maximum Subarray polega na znalezieniu spójnej podtablicy w jednowymiarowej tablicy liczb, która ma największą sumę. Na przykład w tablicy [-2, 1, -3, 4, -1, 2, 1, -5, 4] podtablica [4, -1, 2, 1] daje największą sumę równą 6. Podejście brute force o złożoności O(n²) sprawdza wszystkie podtablice, ale algorytm Kadane’a rozwiązuje ten problem w czasie 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) # 6Intuicja algorytmu Kadane’a
Algorytm Kadane’a wykonuje jedno przejście przez tablicę, utrzymując bieżącą sumę current_sum. Przy każdym elemencie należy zdecydować: czy lepiej rozszerzyć istniejącą podtablicę, czy rozpocząć nową od tego elementu? Jeśli current_sum stanie się ujemne, zaszkodzi każdej przyszłej podtablicy, więc należy rozpocząć od nowa. Rekurencja ma postać 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)) # 6Śledzenie działania algorytmu Kadane’a
Prześledźmy działanie algorytmu Kadane’a dla [-2, 1, -3, 4, -1, 2, 1, -5, 4]: zaczynamy od curr=-2, max=-2. Dla 1: curr=max(1,-2+1)=1, max=1. Dla -3: curr=max(-3,1-3)=-2, max=1. Dla 4: curr=max(4,-2+4)=4, max=4. Dla -1: curr=3, max=4. Dla 2: curr=5, max=5. Dla 1: curr=6, max=6. Dla -5: curr=1. Dla 4: curr=5, max=6. Algorytm poprawnie wskazuje podtablicę kończącą się na indeksie 6 jako optymalną.
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])Zwracanie właściwej podtablicy
Jeśli osoba przeprowadzająca rozmowę poprosi o zwrócenie samej podtablicy, a nie tylko jej sumy, należy śledzić indeksy początku i końca. Przy rozpoczynaniu od nowa (gdy num > current_sum + num) należy zaktualizować temp_start. Podczas aktualizowania max_sum należy zapisać temp_start jako start, a bieżący indeks jako end. Dodaje to narzut O(1) do tego samego algorytmu o złożoności O(n).
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 największego iloczynu podtablicy
Problem Maximum Product Subarray jest trudniejszy niż wariant dotyczący sumy z powodu liczb ujemnych. Dwie liczby ujemne po pomnożeniu dają liczbę dodatnią, więc bardzo ujemny iloczyn może stać się największy po pomnożeniu przez kolejną liczbę ujemną. Dla [2, 3, -2, 4] odpowiedzią jest 6 ([2, 3]). Dla [-2, 0, -1] odpowiedzią jest 0. Na każdym kroku musimy śledzić zarówno największy, jak i najmniejszy iloczyn.
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)Śledzenie zarówno największych, jak i najmniejszych iloczynów
Kluczowa obserwacja jest następująca: na każdej pozycji bieżący największy iloczyn jest jedną z wartości num, max_so_far * num lub min_so_far * num (ta ostatnia pomaga, gdy liczba ujemna zamienia minimum w maksimum). Analogicznie wyznaczamy minimum. Należy jednocześnie zaktualizować oba iloczyny cur_max i cur_min, korzystając z poprzednich wartości, aby w tym samym kroku nie użyć wartości już zaktualizowanych.
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])) # -2Dlaczego min_prod ma znaczenie
Rozważmy [-3, -10, 5]. Po przetworzeniu -3: max=-3, min=-3. Po -10: kandydaci to (-10, 30, 30) → max=30, min=-10. Po 5: kandydaci to (5, 150, -50) → max=150. Bez śledzenia min_prod nie zauważyliby Państwo odwrócenia, które następuje, gdy duże ujemne minimum zostaje pomnożone przez kolejną liczbę ujemną. Zawsze należy obliczać zarówno max, jak i min na podstawie tych samych poprzednich wartości, aby uniknąć błędu odczytu nieaktualnych danych.
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: 150Zera resetują iloczyn
Zero w tablicy resetuje oba bieżące iloczyny do zera, skutecznie dzieląc tablicę na niezależne podtablice. Gdy num = 0, zarówno max_prod * 0 = 0, jak i min_prod * 0 = 0, więc wszystkie trzy wartości kandydujące stają się równe 0, a maksimum z poprzedniego wyniku zostaje zachowane. Nie jest potrzebny żaden specjalny przypadek — ogólny wzór obsługuje zera w naturalny sposób.
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])) # 0Alternatywa: przejście od lewej do prawej i od prawej do lewej
Alternatywne podejście wykonuje przejście od lewej do prawej oraz od prawej do lewej, resetując bieżący iloczyn do 1 po napotkaniu zera. Największa podtablica iloczynowa nigdy nie przechodzi przez zero, więc jeśli liczba ujemna pogorszy wynik w jednym kierunku, przejście w odwrotnym kierunku wykryje zmianę znaku. To podejście jest eleganckie, ale metoda śledzenia min/max jest częściej oczekiwana podczas rozmów rekrutacyjnych.
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 a iloczyn: najważniejsze różnice
Podtablice sum i iloczynów różnią się pod ważnymi względami. W przypadku sum liczby ujemne zawsze szkodzą, więc należy zachłannie rozpoczynać od nowa. W przypadku iloczynów dwie liczby ujemne pomagają, dlatego trzeba śledzić oba skrajne wyniki. Ponadto zera kończą bieżące iloczyny, ale w przypadku sum są tylko umiarkowanie niekorzystne. Podczas rozmowy rekrutacyjnej należy wyraźnie wskazać te różnice i wyjaśnić, dlaczego konieczne jest śledzenie minimum, zanim zostanie napisany 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])) # 24Złożoność i wskazówki dotyczące rozmowy rekrutacyjnej
Zarówno algorytm Kadane’a (maksymalna suma), jak i metoda śledzenia min/max (maksymalny iloczyn) działają w czasie O(n) i zużywają O(1) pamięci. Najważniejsze wskazówki dotyczące rozmowy rekrutacyjnej: (1) W przypadku maksymalnej sumy warto wspomnieć o alternatywie „Divide and Conquer” o złożoności O(n log n), aby pokazać szerszą znajomość tematu. (2) W przypadku maksymalnego iloczynu należy podkreślić, że min_prod i max_prod są aktualizowane jednocześnie na podstawie poprzednich wartości, aby uniknąć użycia nieaktualnych danych. (3) Zawsze należy doprecyzować: czy tablica może być pusta? Czy podtablica musi być niepusta? (Tak, zgodnie z konwencją musi być niepusta.)
# 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 negativeSzybki test
Proszę sprawdzić, jak dobrze rozumieją Państwo zagadnienia Data Structures & Algorithms — Coding Interview Prep omówione w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo: algorytm Kadane’a rozwiązuje problem Maximum Subarray w czasie O(n), wybierając przy każdym elemencie rozszerzenie podtablicy lub rozpoczęcie jej od nowa, problem Maximum Product Subarray wymaga śledzenia zarówno najmniejszych, jak i największych bieżących iloczynów z powodu odwracania znaku przez liczby ujemne oraz zera w naturalny sposób resetują bieżący iloczyn bez specjalnego kodu. Następnie omówimy problem Word Break z użyciem jednowymiarowej tablicy DP.
Często zadawane pytania
Czy lekcja „Maksymalna podtablica i podtablica o maksymalnym iloczynie” jest bezpłatna?
Tak — pełny tekst „Maksymalna podtablica i podtablica o maksymalnym iloczynie” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Maksymalna podtablica i podtablica o maksymalnym iloczynie”?
Zastosują Państwo algorytm Kadane’a do zadania maximum-sum-subarray i rozszerzą go tak, aby śledzić jednocześnie maksimum i minimum w wariancie iloczynowym. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Maksymalna podtablica i podtablica o maksymalnym iloczynie”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- House Robber: rekurencja wybierz albo pomiń
- Maksymalna podtablica i podtablica o maksymalnym iloczynie
- Word Break i dzielenie ciągu na segmenty
- Decode Ways i zliczanie ścieżek