Prodotto massimo della sottosequenza contigua su $ mathbb {r} $

Question

Per il problema di una sottosequenza del prodotto massimo con numeri interi negativi, zero e positivi, ho la seguente soluzione di lavoro (ispirazione da qui).

Mostriamo prima come risolvere il problema quando l'array non contiene zero:

• Se c'è una singola voce, restituire la voce.

• Se il numero di voci negative è pari, restituire il prodotto di tutti gli elementi.

• Altrimenti, lascia che l'array sia $ A_1, ldots, a_n $, lascia che l'indice del primo elemento negativo sia $ i $, e lascia che l'indice dell'ultimo elemento negativo sia $ j $. Ritorno$$ max left ( Prod_ {k = i+1}^n a_k, Prod_ {k = 1}^{j-1} a_k a destra). $$(Da $ n> 1 $, entrambe le somme non sono vuote.)

Per un array generale che non è tutti zero, partiamo in massimi subarray senza zero, applicare la procedura precedente a ciascun subarray e restituire il massimo su tutte le uscite.

Oltre a questa soluzione, ho anche una soluzione di programmazione dinamica ispirata in gran parte dal problema della somma di somma massima che funziona per numeri reali positivi ma non per numeri negativi.

Dato un array $ A_1, ldots, a_n> 0 $, calcoliamo un array $ S_1, ldots, s_n $ tale che $ S_i $ è il prodotto massimo di una sottosequenza di $ A_1, ldots, a_i $ contenente $ A_i $: $$ s_1 = a_1, s_ {i+1} = max (a_ {i+1}, s_i a_ {i+1}). $$La risposta è quindi $ max (s_1, ldots, s_n) $.

Vorrei sapere come cambiare la prima soluzione per gestire i numeri generali piuttosto che solo interi e capire come funzionano questi cambiamenti.

Ho provato a trovare una struttura di dati per il problema con i numeri a punta mobile, ho pensato di usare $ P _ { min} $ e $ P _ { max} $ matrici dove $ P _ { min i, j}/p _ { max i, j} $ è il prodotto minimo/massimo che può essere calcolato da una sottosequenza in $ A_i, ldots, a_j $ In seguito, ma non sono riuscito a trovare una relazione ricorsiva tra gli elementi delle matrici. Penso di aver trovato una sorta di metodo euristico usando $ P _ { min} $ e $ P _ { max} $ come vettori che vengono aggiornati in un'unica iterazione di $ A $, ogni valore di $ P _ { min} $ a seconda di $ A $ e $ P _ { max} $, e ogni valore di $ P _ { max} $ a seconda di $ A $ e $ P _ { min} $, ma non ho testato quanto sia adeguato.

Un esempio del perché il primo algoritmo nella mia domanda non funziona per i numeri a punto mobile è l'input $2, 2, 0.1, 2, 2$.