Maximum product of contiguous subsequence over $\mathbb{R}$

Question

For the problem of a subsequence of maximum product with negative, zero and positive integers, I have the following working solution (inspiration from here).

Let us first show how to solve the problem when the array contains no zeroes:

• If there is a single entry, return the entry.

• If the number of negative entries is even, return the product of all elements.

• Otherwise, let the array be $A_1,\ldots,A_n$, let the index of the first negative element be $i$, and let the index of the last negative element be $j$. Return $$ \max \left( \prod_{k=i+1}^n A_k, \prod_{k=1}^{j-1} A_k \right). $$ (Since $n > 1$, both sums are non-empty.)

For a general array which is not all zeroes, we partition in into maximal subarrays with no zeroes, apply the preceding procedure to each subarray, and return the maximum over all outputs.

Besides this solution, I also have a dynamic programming solution inspired largely from the problem of maximum sum subsequence that works for positive real numbers but not for negative numbers.

Given an array $A_1,\ldots,A_n > 0$, we compute an array $S_1,\ldots,S_n$ such that $S_i$ is the maximum product of a subsequence of $A_1,\ldots,A_i$ containing $A_i$: $$ S_1 = A_1, S_{i+1} = \max(A_{i+1}, S_i A_{i+1}). $$ The answer is then $\max(S_1,\ldots,S_n)$.

I would like to know how to change the first solution to handle general numbers rather than only integers, and to understand how these changes work.

I tried to find a data structure for the problem with floating-point numbers, I thought of using $P_{\min}$ and $P_{\max}$ matrices where $P_{\min\ i, j}/P_{\max\ i,j}$ is the minimum/maximum product that can be computed from a subsequence in the $A_i,\ldots,A_j$ subsequence, but I could not find a recursive relation between the elements of the matrices. I think I found some sort of heuristic method using $P_{\min}$ and $P_{\max}$ as vectors that are updated in a single iteration of $A$, each value of $P_{\min}$ depending on $A$ and $P_{\max}$, and each value of $P_{\max}$ depending on $A$ and $P_{\min}$, but I did not test how adequate it is.

An example of why the first algorithm in my question is not working for floating-point numbers is the input $2, 2, 0.1, 2, 2$.

Answer 1

You can adopt the dynamic programming solution; the other solution looks harder to adapt.

Given an array $A_1,\ldots,A_n$, we let $P_i$ be the maximum positive product of a subsequence of $A_1,\ldots,A_i$ containing $A_i$, and we let $N_i$ be the minimum negative product of such a subsequence. If no such subsequences exist, we let $P_i = 0$ or $N_i = 0$.

Initialization:

• If $A_1 = 0$ then $P_1 = N_1 = 0$.
• If $A_1 > 0$ then $P_1 = A_1$ and $N_1 = 0$.
• If $A_1 < 0$ then $P_1 = 0$ and $N_1 = A_1$.

Iteration:

• If $A_i = 0$ then $P_i = N_i = 0$.
• If $A_i > 0$ then $P_i = \max(A_i, A_i P_{i-1})$ and $N_i = A_i N_{i-1}$.
• If $A_i < 0$ then $P_i = A_i N_{i-1}$ and $N_i = \min(A_i, A_i P_{i-1})$.

If $\max(P_1,\ldots,P_n) > 0$, then this is the answer. The only way in which this fails to happen is if there is no subsequence whose product is positive. This can only happen if the array contains only negative numbers and zeroes, and every two negative numbers are separated by at least one zero. If there is at least one zero, then the answer is zero. If there are no zeroes, then $n = 1$, and the answer is $A_1$.