Pergunta

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$.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top