Maximum Product Subarray

+10

Moltiplica tra loro gli elementi di un sottoarray di nums e restituisci il prodotto più grande ottenibile da qualsiasi sottoarray. Un sottoarray contiene elementi consecutivi, senza intervalli, e non è mai vuoto, quindi anche un array di valori negativi ha una risposta. Sono consentiti zeri e valori negativi.

Funzione

maxProduct(nums: integer-array) → integer

numsinteger-array: gli interi da moltiplicare, ciascuno compreso tra -10 e 10
Restituisceinteger: il prodotto più grande di un sottovettore non vuoto

Vincoli

1 ≤ nums.length ≤ 2 × 10⁴
-10 ≤ nums[i] ≤ 10
Il prodotto di ogni sottovettore rientra in un intero con segno a 32 bit.

Esempi

Input: nums = [2, -5, 3, -2, 0, 4]
Output: 60
Spiegazione: I due numeri negativi si annullano: 2 × -5 × 3 × -2 = 60. Lo 0 divide l'array in due, e il 4 dall'altra parte non può superare 60.

Input: nums = [-2, 3, -4, -1]
Output: 24
Spiegazione: L'intero array si moltiplica dando -24 perché contiene tre numeri negativi. Escludendo l'ultimo elemento ne restano due: -2 × 3 × -4 = 24, che è maggiore del 12 che ottieni escludendo il primo elemento.

Input: nums = [-6, 0, -7]
Output: 0
Spiegazione: Un sottoarray che evita lo 0 è un singolo numero negativo, mentre un sottoarray che contiene lo 0 ha come prodotto 0. La scelta migliore è il sottoarray [0].

Per approfondire

Come indicheresti anche dove inizia e finisce il sottoarray migliore, sempre in tempo O(n) e con spazio O(1)?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Moltiplicare per un numero negativo inverte l’ordine dei prodotti, quindi il prodotto più piccolo finora può diventare il più grande al passaggio successivo, mentre uno zero azzera tutti i prodotti. Memorizza due valori a ogni indice invece di uno: il prodotto più grande e quello più piccolo di un sottoarray che termina lì; basta un solo passaggio.

Moltiplica ogni sottovettore a partire da ciascun punto iniziale

Corretto, ma non termina sui test più grandi

Intuizione

Fissa un indice iniziale e sposta la fine verso destra, moltiplicando un product progressivo per ogni nuovo elemento. Confrontarlo con il migliore dopo ogni passaggio copre ogni sottovettore una sola volta. Inizia best da nums[0], perché la risposta può essere negativa.

Ci sono circa n²/2 coppie di indici iniziali e finali, una moltiplicazione ciascuna: 2 × 10^8 per 20.000 elementi.

Algoritmo

Imposta best su nums[0].
Per ogni start, imposta product su 1.
Sposta end da start fino all'ultimo indice e moltiplica product per nums[end].
Se product è maggiore di best, memorizzalo.
Restituisci 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

Scansiona da entrambe le estremità, ricominciando dagli zeri

Intuizione

Gli zeri dividono l'array in segmenti senza zeri. All'interno di un segmento ogni valore ha modulo almeno 1, quindi un sottarray più lungo non ha mai un prodotto in valore assoluto più piccolo; cambia solo il segno. Con un numero pari di valori negativi, il segmento intero è la scelta migliore. Con un numero dispari, bisogna eliminare un valore negativo e il taglio migliore esclude il primo valore negativo e tutto ciò che lo precede, oppure l'ultimo valore negativo e tutto ciò che lo segue. In entrambi i casi si mantiene un suffisso o un prefisso del segmento.

Una scansione da sinistra con un prodotto progressivo controlla ogni prefisso, reimpostando il prodotto a 1 dopo uno 0. Una scansione da destra controlla ogni suffisso. Su [-2, 3, -4, -1] la scansione da sinistra calcola -2, -6, 24 e -24; quella da destra -1, 4, 12 e -24, quindi la risposta è 24. L'argomento richiede che ogni valore diverso da zero abbia modulo almeno 1, condizione che vale per gli interi.

Algoritmo

Imposta best su nums[0] e product su 1.
Procedi da sinistra a destra: moltiplica product per ogni elemento e mantieni il maggiore tra best e product.
Ogni volta che product diventa 0, reimpostalo a 1 in modo che la scansione successiva riparta da zero.
Imposta di nuovo product su 1 e procedi nello stesso modo da destra a sinistra.
Restituisci 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

Traccia il prodotto più grande e quello più piccolo che terminano qui

Intuizione

Ogni sottoarray che termina all'indice i è nums[i] da solo, oppure nums[i] moltiplicato per un sottoarray che termina a i-1. Quando nums[i] è negativo, il prodotto più grande tra questi si ottiene dal prodotto più piccolo che termina a i-1. Quindi tieni entrambi: high e low, i prodotti più grande e più piccolo di un sottoarray che termina all'indice corrente. Il nuovo high è il più grande tra num, high × num e low × num, mentre il nuovo low è il più piccolo. Considerare num da solo è ciò che riavvia la sequenza dopo uno zero.

Nel primo esempio low è -30 quando arriva -2, e -30 × -2 = 60 diventa high, la risposta.

Algoritmo

Imposta high, low e best su nums[0].
Per ogni elemento successivo num, calcola a = high × num e b = low × num.
Imposta high sul più grande e low sul più piccolo tra num, a e b.
Imposta best sul più grande tra best e high.
Restituisci 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

Trappole e casi limite

Tenere traccia solo del prodotto più grande. Nel primo esempio restituisce 4 invece di 60, perché scarta il -30 che il -2 trasforma in 60.
Calcolare il nuovo low a partire da high già aggiornato. Salva high × num e low × num prima di modificare uno dei due.
Inizializzare best a 0 o 1. [-3] deve restituire -3, perché il sottoarray non può essere vuoto.
Eseguire solo il passaggio da sinistra a destra del metodo a due passaggi. Su [-2, 3, 4] non vede mai un valore superiore a -2, ma il suffisso [3, 4] dà 12.
In JavaScript, TypeScript e Lua, 0 moltiplicato per un numero negativo è -0, che viene stampato con il segno meno. Aggiungi 0 al risultato prima di restituirlo.

Domande frequenti3

Qual è la complessità temporale del sottarray a prodotto massimo?

Tenere traccia del prodotto più grande e di quello più piccolo che terminano a ciascun indice richiede un tempo O(n) e uno spazio O(1). Il metodo a due passate con prefissi e suffissi ha lo stesso costo. Moltiplicare ogni sottovettore a partire da ciascun punto iniziale richiede un tempo O(n²).

Perché serve il prodotto minimo nel sottarray a prodotto massimo?

Un numero negativo trasforma il prodotto più negativo che termina all’indice precedente in quello più grande. Conserva solo il prodotto più grande e quel candidato non ci sarà più quando ti servirà. In [3, -2, -4], il prodotto più piccolo prima di -4 è -6, e -6 × -4 = 24 è la risposta.

In che modo Maximum Product Subarray è diverso da Maximum Subarray?

Per le somme, un totale progressivo negativo è sempre svantaggioso, quindi basta un solo valore per indice. Per i prodotti, un prodotto progressivo negativo può diventare il migliore dopo un altro numero negativo, mentre zero azzera tutto. Perciò, nella versione per i prodotti, si tengono il prodotto più grande e quello più piccolo a ogni indice.

def maxProduct(nums):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso

Maximum Product Subarray

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Moltiplica ogni sottovettore a partire da ciascun punto iniziale

Scansiona da entrambe le estremità, ricominciando dagli zeri

Traccia il prodotto più grande e quello più piccolo che terminano qui

Trappole e casi limite

Domande frequenti3

Problemi simili