Subarray a somma massima e subarray a prodotto massimo

Il problema Maximum Subarray consiste nel trovare il sottoarray contiguo all'interno di un array unidimensionale di numeri che abbia la somma più grande. Ad esempio, in [-2, 1, -3, 4, -1, 2, 1, -5, 4], il sottoarray [4, -1, 2, 1] produce la somma massima, pari a 6. Un approccio a forza bruta O(n²) verifica tutti i sottoarray, mentre l'algoritmo di Kadane risolve il problema in O(n).

L'algoritmo di Kadane attraversa l'array una sola volta, mantenendo una current_sum progressiva. A ogni elemento occorre decidere: conviene estendere il sottoarray esistente oppure iniziare un nuovo sottoarray da questo elemento? Se current_sum diventa negativo, danneggerebbe qualsiasi sottoarray futuro, quindi si ricomincia. La ricorrenza è current_sum = max(num, current_sum + num).

Vediamo passo per passo l'algoritmo di Kadane su [-2, 1, -3, 4, -1, 2, 1, -5, 4]: si inizia con curr=-2, max=-2. Con 1: curr=max(1,-2+1)=1, max=1. Con -3: curr=max(-3,1-3)=-2, max=1. Con 4: curr=max(4,-2+4)=4, max=4. Con -1: curr=3, max=4. Con 2: curr=5, max=5. Con 1: curr=6, max=6. Con -5: curr=1. Con 4: curr=5, max=6. L'algoritmo identifica correttamente come ottimale il sottoarray che termina all'indice 6.

Se durante il colloquio Le viene chiesto di restituire il sottoarray stesso, e non soltanto la somma, deve tenere traccia degli indici iniziale e finale. Quando ricomincia, perché num > current_sum + num, aggiorni un temp_start. Quando aggiorna max_sum, salvi temp_start come start e l'indice corrente come end. Questo aggiunge un sovraccarico O(1) allo stesso algoritmo O(n).

Il problema Maximum Product Subarray è più complesso della variante basata sulla somma a causa dei numeri negativi. Il prodotto di due numeri negativi è positivo, quindi un prodotto molto negativo può diventare il massimo dopo essere stato moltiplicato per un altro numero negativo. Per [2, 3, -2, 4], la risposta è 6 ([2, 3]). Per [-2, 0, -1], la risposta è 0. A ogni passaggio è necessario tenere traccia sia del prodotto massimo sia di quello minimo.

L'intuizione fondamentale è la seguente: in ogni posizione, il prodotto massimo corrente è uno tra num, max_so_far * num e min_so_far * num; quest'ultimo è utile quando un numero negativo trasforma il minimo in un massimo. Lo stesso vale per il minimo. Aggiorni entrambi cur_max e cur_min simultaneamente usando i valori precedenti, così da evitare di usare valori già aggiornati nello stesso passaggio.

Consideri [-3, -10, 5]. Dopo aver elaborato -3: max=-3, min=-3. Dopo -10: i candidati sono (-10, 30, 30) → max=30, min=-10. Dopo 5: i candidati sono (5, 150, -50) → max=150. Senza tenere traccia di min_prod, non rileverebbe l'inversione che si verifica quando un minimo molto negativo viene moltiplicato per un altro numero negativo. Calcoli sempre sia max sia min usando gli stessi valori precedenti, per evitare un bug dovuto alla lettura di valori obsoleti.

Uno zero nell'array azzera entrambi i prodotti progressivi, separando di fatto l'array in sottoarray indipendenti. Quando num = 0, sia max_prod * 0 = 0 sia min_prod * 0 = 0, quindi tutti e tre i candidati diventano 0 e il risultato massimo precedente viene preservato. Non è necessario alcun codice per casi speciali: la formula generale gestisce gli zeri naturalmente.

Un approccio alternativo esegue una scansione da sinistra a destra e da destra a sinistra, reimpostando il prodotto progressivo a 1 quando incontra uno zero. Il sottoarray a prodotto massimo non attraversa mai uno zero, quindi, se un numero negativo produce un risultato sfavorevole in una direzione, la scansione inversa rileverà l'inversione. Questo approccio è elegante, ma il metodo di tracciamento di min/max è quello più comunemente richiesto nei colloqui.

I sottoarray basati sulla somma e quelli basati sul prodotto differiscono in modi importanti. Per la somma, i numeri negativi sono sempre dannosi, quindi si ricomincia in modo greedy. Per il prodotto, due numeri negativi sono utili, quindi è necessario tenere traccia di entrambi gli estremi. Inoltre, gli zeri sono terminali per i prodotti, mentre sono solo moderatamente dannosi per le somme. Durante un colloquio, riconosca esplicitamente queste differenze e spieghi perché è necessario tenere traccia di min prima di scrivere il codice.

Sia l'algoritmo di Kadane, per la somma massima, sia il tracciamento di min/max, per il prodotto massimo, richiedono tempo O(n) e spazio O(1). Consigli importanti per il colloquio: (1) per la somma massima, menzioni l'alternativa divide et impera O(n log n) per dimostrare una conoscenza più ampia; (2) per il prodotto massimo, sottolinei che aggiorna min_prod e max_prod simultaneamente usando i valori precedenti, così da evitare dati obsoleti; (3) chiarisca sempre: l'array può essere vuoto? Il sottoarray deve essere non vuoto? Per convenzione, sì, deve essere non vuoto.

Metta alla prova la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.

In questa lezione ha imparato: l'algoritmo di Kadane risolve il problema del sottoarray a somma massima in O(n), scegliendo a ogni elemento se estendere il sottoarray o ricominciare, il problema del sottoarray a prodotto massimo richiede di tenere traccia sia dei prodotti progressivi minimo e massimo a causa delle inversioni provocate dai numeri negativi e gli zeri reimpostano naturalmente il prodotto progressivo senza codice per casi speciali. Nella prossima lezione esamineremo il problema Word Break usando una tabella DP 1D.