Segenza massima del prodotto

Question

Devo trovare il prodotto massimo di una sottosequenza in sequenza di numeri interi n. Sto cercando un algoritmo, non necessariamente espresso come codice.

Esempio:

1. In: 3,1, -2,4. Out: 4.
2. In: 2,5, -1, -2, -4. Fuori: 20. (2 * 5 * -1 * -2).

ho fatto un algoritmo in O(n²), ma ora ho bisogno di uno in O(n).
So che è possibile.

Come è possibile farlo in O(n)?

Answer 1

Se tutto il tuo input era> 0, il prodotto massimo verrebbe trovato moltiplicando tutti i numeri insieme.

Se tutto il tuo input era diverso da 0 e aveva un numero pari di numeri negativi, di nuovo il prodotto massimo sarebbe stato trovato moltiplicando tutti i numeri.

Quindi il lavoro riguarda gli zeri e i numeri negativi.

È necessario eseguire l'elenco una sola volta, calcolando il prodotto in esecuzione man mano che si procede. Se raggiungi uno 0, allora tutto ciò che precede è un sottoinsieme candidato e i suoi particolari (indice iniziale, indice finale, prodotto) devono essere salvati se è meglio del migliore finora trovato. Ora avvia un nuovo prodotto in esecuzione. Se raggiungi un numero negativo, quell'elemento è un'interruzione condizionata nel totale parziale. Il prodotto in esecuzione senza utilizzare il numero negativo sarebbe valutato al meglio. Ma ora hai bisogno di avere 2 prodotti in esecuzione, quello con il numero negativo e uno nuovo. Quindi i multipli successivi devono lavorare contro 2 liste. A questo punto avrei 2 prodotti in esecuzione. Se si colpisce un altro numero negativo, ciascuna delle proprie liste di corsa deve essere bisecata come descritto in precedenza. Quindi potresti finire con un sacco di liste in esecuzione se non hai potato. Penso che sia possibile sfoltire le liste correnti per tenere traccia solo di 3: la sottolista appena iniziata, la lista continua con numero dispari di numeri negativi e un numero pari di numeri negativi. Qualsiasi sottolista candidato che non fa parte della moltiplicazione in corso dovrebbe essere valutato per vedere che è il migliore prima di rilasciarlo.

Alla fine sua O (n)

Answer 2

Il prodotto massima sottosequenza di una serie di numeri diversi da zero o è il prodotto di tutti i numeri (se c'è un numero pari di numeri negativi), oppure è il maggiore del prodotto di tutti i numeri dopo il primo numero negativo e il prodotto di tutti i numeri fino all'ultimo numero negativo.

Questo fornisce una soluzione O (N): interrompe la sequenza in serie di numeri diversi da zero e applica la regola nel primo paragrafo a ciascuna. Scegli il massimo di questi.

codice Python C-like per questo:

def prod(seq, a, b): 
    r = 1 
    for i in xrange(a, b): 
     r *= seq[i] 
    return r 

def maxprodnon0(seq, a, b): 
    firstneg = -1 
    negs = 0 
    for i in xrange(a, b): 
     if seq[i] >= 0: continue 
     negs += 1 
     if firstneg < 0: 
      firstneg = i 
     lastneg = i 
    if negs % 2 == 0: return prod(seq, a, b) 
    return max(prod(seq, firstneg + 1, b), prod(seq, a, lastneg)) 

def maxprod(seq): 
    best = 0 
    N = len(seq) 
    i = 0 
    while i < N: 
     while i < N and seq[i] == 0: 
      i += 1 
     j = i 
     while j < N and seq[j] != 0: 
      j += 1 
     best = max(best, maxprodnon0(seq, i, j)) 
     i = j 
    return best 

for case in [2,5,-1,-2,-4], [1,2,0,-4,5,6,0,7,1], [1,2,0,-4,5,6,-1,-1,0,7,1]: 
    print maxprod(case)