Maximum Product Subarray

+10

Pomnóż przez siebie elementy podtablicy nums i zwróć największy iloczyn, jaki może dać dowolna podtablica. Podtablica składa się z kolejnych elementów bez przerw i nigdy nie jest pusta, więc nawet tablica zawierająca liczby ujemne ma odpowiedź. Zera i wartości ujemne są dozwolone.

Funkcja

maxProduct(nums: integer-array) → integer

numsinteger-array: liczby całkowite do pomnożenia, każda z zakresu od -10 do 10
Zwracainteger: największy iloczyn niepustej podtablicy

Ograniczenia

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
Iloczyn każdej podtablicy mieści się w 32-bitowej liczbie całkowitej ze znakiem.

Przykłady

Wejście: nums = [2, -5, 3, -2, 0, 4]
Wyjście: 60
Wyjaśnienie: Dwie liczby ujemne się znoszą: 2 × -5 × 3 × -2 = 60. 0 dzieli tablicę na dwie części, a 4 po drugiej stronie nie może przebić 60.

Wejście: nums = [-2, 3, -4, -1]
Wyjście: 24
Wyjaśnienie: Iloczyn całej tablicy wynosi -24, ponieważ zawiera ona trzy liczby ujemne. Pominięcie ostatniego elementu pozostawia dwie z nich: -2 × 3 × -4 = 24, co daje więcej niż 12, które otrzymujesz po pominięciu pierwszego elementu.

Wejście: nums = [-6, 0, -7]
Wyjście: 0
Wyjaśnienie: Podtablica, która nie zawiera 0, składa się z jednej liczby ujemnej, a podtablica zawierająca 0 ma iloczyn równy 0. Najlepszym wyborem jest podtablica [0].

Pytanie dodatkowe

Jak dodatkowo wskazać, gdzie zaczyna się i kończy najlepsza podtablica, nadal w czasie O(n) i przy użyciu O(1) pamięci?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Mnożenie przez liczbę ujemną odwraca kolejność iloczynów, więc najmniejszy dotąd iloczyn może w następnym kroku stać się największy, a zero zeruje wszystkie iloczyny. Przechowuj w każdym indeksie dwie wartości zamiast jednej: największy i najmniejszy iloczyn podtablicy kończącej się w tym miejscu. Wystarczy jedno przejście.

Pomnóż każdą podtablicę rozpoczynającą się w danym miejscu

Poprawne, ale nie kończy się na największych testach

Intuicja

Ustal indeks początkowy i przesuwaj koniec w prawo, mnożąc bieżący product przez każdy nowy element. Porównywanie go z najlepszym wynikiem po każdym kroku sprawia, że każdy podciąg jest uwzględniany dokładnie raz. Ustaw best na nums[0], ponieważ odpowiedź może być ujemna.

Istnieje około n²/2 par indeksów początkowych i końcowych, czyli jedno mnożenie na parę: 2 × 10^8 dla 20,000 elementów.

Algorytm

Ustaw best na nums[0].
Dla każdego start ustaw product na 1.
Przesuwaj end od start do ostatniego indeksu i mnoż product przez nums[end].
Jeśli product jest większy niż best, zapisz go.
Zwróć best.

def maxProduct(nums):
    n = len(nums)
    best = nums[0]
    for start in range(n):
        product = 1
        for end in range(start, n):
            # product is now the product of nums[start..end]
            product *= nums[end]
            if product > best:
                best = product
    return best

Skanuj od obu końców, zaczynając od nowa przy zerach

Intuicja

Zera dzielą tablicę na ciągi bez zer. W obrębie takiego ciągu każda wartość ma wartość bezwzględną co najmniej 1, więc dłuższa podtablica nigdy nie ma mniejszej wartości bezwzględnej iloczynu; zmienia się tylko znak. Gdy liczba liczb ujemnych jest parzysta, najlepszy jest cały ciąg. Gdy jest nieparzysta, trzeba usunąć jedną liczbę ujemną, a najlepsze cięcie usuwa pierwszą liczbę ujemną i wszystko przed nią albo ostatnią liczbę ujemną i wszystko po niej. W obu przypadkach zostaje sufiks lub prefiks ciągu.

Przejście od lewej z bieżącym iloczynem sprawdza każdy prefiks, resetując iloczyn do 1 po napotkaniu 0. Przejście od prawej sprawdza każdy sufiks. Dla [-2, 3, -4, -1] przejście od lewej daje kolejno -2, -6, 24 i -24, a przejście od prawej: -1, 4, 12 i -24, więc odpowiedzią jest 24. To rozumowanie wymaga, aby każda niezerowa wartość miała wartość bezwzględną co najmniej 1, co zachodzi dla liczb całkowitych.

Algorytm

Ustaw best na nums[0], a product na 1.
Przejdź od lewej do prawej: pomnóż product przez każdy element i zachowaj większą z wartości best i product.
Gdy product osiągnie 0, ustaw go ponownie na 1, aby następny przebieg rozpoczął się od nowa.
Ponownie ustaw product na 1 i wykonaj ten sam przebieg od prawej do lewej.
Zwróć best.

def maxProduct(nums):
    best = nums[0]
    # Left to right: the product of every prefix of each zero-free run
    product = 1
    for num in nums:
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1  # a zero ends the run, the next one starts fresh
    # Right to left: the product of every suffix of each zero-free run
    product = 1
    for num in reversed(nums):
        product *= num
        best = max(best, product)
        if product == 0:
            product = 1
    return best

Śledź największy i najmniejszy iloczyn kończący się tutaj

Intuicja

Każda podtablica kończąca się na indeksie i składa się tylko z nums[i] albo z nums[i] pomnożonego przez podtablicę kończącą się na indeksie i-1. Gdy nums[i] jest ujemne, największy z tych iloczynów powstaje z najmniejszego iloczynu kończącego się na indeksie i-1. Dlatego zachowujemy obie wartości: high i low — największy i najmniejszy iloczyn podtablicy kończącej się na bieżącym indeksie. Nowe high to największa z wartości num, high × num i low × num, a nowe low to najmniejsza z nich. Wzięcie samego num rozpoczyna ciąg od nowa po zerze.

W pierwszym przykładzie, gdy pojawia się -2, low wynosi -30, a -30 × -2 = 60 staje się wartością high i jest odpowiedzią.

Algorytm

Ustaw high, low i best na nums[0].
Dla każdego kolejnego elementu num oblicz a = high × num i b = low × num.
Ustaw high na największą, a low na najmniejszą z wartości: num, a i b.
Ustaw best na większą z wartości best i high.
Zwróć best.

def maxProduct(nums):
    # high and low: the largest and smallest product of a subarray ending at the current index
    high = low = best = nums[0]
    for num in nums[1:]:
        # Multiply both old values first: a negative num swaps their roles
        a = high * num
        b = low * num
        high = max(num, a, b)
        low = min(num, a, b)
        best = max(best, high)
    return best

Pułapki i przypadki brzegowe

Śledzenie tylko największego iloczynu. W pierwszym przykładzie zwraca to 4 zamiast 60, ponieważ pomija -30, które -2 zamienia w 60.
Obliczanie nowego low na podstawie już zaktualizowanego high. Zapisz high × num i low × num przed zmianą którejkolwiek z tych wartości.
Ustawianie best na 0 lub 1. [-3] musi zwrócić -3, ponieważ podtablica nie może być pusta.
Wykonanie tylko lewego przebiegu metody dwuprzebiegowej. Dla [-2, 3, 4] nigdy nie napotka wartości większej niż -2, ale sufiks [3, 4] daje 12.
W JavaScript, TypeScript i Lua 0 pomnożone przez liczbę ujemną daje -0, które jest wyświetlane ze znakiem minus. Przed zwróceniem wyniku dodaj do niego 0.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu maksymalnego iloczynu podtablicy?

Śledzenie największego i najmniejszego iloczynu kończącego się na każdym indeksie zajmuje O(n) czasu i O(1) pamięci. Dwuprzebiegowa metoda prefiksów i sufiksów kosztuje tyle samo. Mnożenie elementów każdej podtablicy, zaczynając od każdego indeksu, zajmuje O(n²) czasu.

Dlaczego w problemie Maximum Product Subarray potrzebny jest produkt minimalny?

Liczba ujemna zamienia najmniejszy iloczyn kończący się na poprzednim indeksie w największy. Zachowaj tylko największy iloczyn, a gdy będzie potrzebny, ten kandydat już zniknie. W [3, -2, -4] najmniejszy iloczyn przed -4 wynosi -6, a -6 × -4 = 24 to odpowiedź.

Czym różni się podtablica o maksymalnym iloczynie od podtablicy o maksymalnej sumie?

W przypadku sum ujemna suma bieżąca tylko szkodzi, więc wystarczy jedna wartość dla każdego indeksu. W przypadku iloczynów ujemny iloczyn bieżący może stać się największy po pomnożeniu przez kolejną liczbę ujemną, a zero resetuje wszystko. Dlatego w wersji dla iloczynów przechowuje się największy i najmniejszy iloczyn dla każdego indeksu.

def maxProduct(nums):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

nums = [2, -5, 3, -2, 0, 4]

Oczekiwany wynik

Maximum Product Subarray

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Pomnóż każdą podtablicę rozpoczynającą się w danym miejscu

Skanuj od obu końców, zaczynając od nowa przy zerach

Śledź największy i najmniejszy iloczyn kończący się tutaj

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania