Produit maximum d'une subséquence contiguë sur $ mathbb {r} $

Question

Pour le problème d'une sous-séquence de produit maximum avec des entiers négatifs, zéro et positifs, j'ai la solution de travail suivante (inspiration de ici).

Montrez d'abord comment résoudre le problème lorsque le tableau ne contient aucun zéros:

• S'il y a une seule entrée, retournez l'entrée.

• Si le nombre d'entrées négatives est uniforme, retournez le produit de tous les éléments.

• Sinon, laissez le tableau $ A_1, ldots, a_n $, que l'indice du premier élément négatif soit $ i $, et laissez l'indice du dernier élément négatif être $ j $. Revenir$$ max Left ( prod_ {k = i + 1} ^ n a_k, prod_ {k = 1} ^ {j-1} a_k droit). $$(Depuis $ n> 1 $, les deux sommes sont non vides.)

Pour un tableau général qui n'est pas tous des zéros, nous partitions dans des sous-réseaux maximaux sans zéros, appliquons la procédure précédente à chaque sous-réseau et renvoyons le maximum sur toutes les sorties.

Outre cette solution, j'ai également une solution de programmation dynamique inspirée en grande partie du problème de la sous-séquence de somme maximale qui fonctionne pour des nombres réels positifs mais pas pour des nombres négatifs.

Étant donné un tableau $ A_1, ldots, a_n> 0 $, nous calculons un tableau $ S_1, ldots, s_n $ tel que $ S_i $ est le produit maximum d'une sous-séquence de $ A_1, ldots, a_i $ contenant $ A_i $: $$ s_1 = a_1, s_ {i + 1} = max (a_ {i + 1}, s_i a_ {i + 1}). $$La réponse est alors $ max (s_1, ldots, s_n) $.

Je voudrais savoir comment changer la première solution pour gérer les nombres généraux plutôt que uniquement des entiers, et pour comprendre comment ces changements fonctionnent.

J'ai essayé de trouver une structure de données pour le problème avec les nombres à virgule flottante, j'ai pensé à utiliser $ P _ { min} $ et $ P _ { max} $ matrices où $ P _ { min i, j} / p _ { max i, j} $ est le produit minimum / maximum qui peut être calculé à partir d'une sous-séquence du $ A_i, ldots, a_j $ La subséquence, mais je n'ai pas pu trouver de relation récursive entre les éléments des matrices. Je pense que j'ai trouvé une sorte de méthode heuristique en utilisant $ P _ { min} $ et $ P _ { max} $ en tant que vecteurs mis à jour dans une seule itération de $ A $, chaque valeur de $ P _ { min} $ selon $ A $ et $ P _ { max} $, et chaque valeur de $ P _ { max} $ selon $ A $ et $ P _ { min} $, mais je n'ai pas testé à quel point il est suffisant.

Un exemple de la raison pour laquelle le premier algorithme de ma question ne fonctionne pas pour les nombres à virgule flottante est l'entrée $2, 2, 0.1, 2, 2$.