1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Can you replace the C code with a concise specification of the problem? It would help to list the inputs, the desired output, and how the output relates or is determined by the input. Not all of us read C code; C code is a particularly wordy way to specify a problem; and that's an awful lot of code for someone to read just to understand what problem you are trying to solve. Thank you! $\endgroup$ – D.W. Feb 5 at 8:39
  • 1
    $\begingroup$ You might refer to cs.stackexchange.com/tags/dynamic-programming/info and try applying the techniques there, then show us in the question what progress you've made and where you got stuck. $\endgroup$ – D.W. Feb 5 at 8:40
  • $\begingroup$ The point of pseudocode is that you don’t need functions like produs at all. $\endgroup$ – Yuval Filmus Feb 8 at 8:59
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think that the last call to max in the Iteration section should be min. $\endgroup$ – silviubogan Feb 9 at 7:45
  • $\begingroup$ Thanks, corrected. $\endgroup$ – Yuval Filmus Feb 9 at 7:52
  • $\begingroup$ How can I find the beginning and end indices of the maximum product subsequence? $\endgroup$ – silviubogan Feb 14 at 7:17
  • $\begingroup$ You have to carry this information through the dynamic programming recurrence: whenever you assign $P_i$ or $N_i$ some value, you also have enough information to store the corresponding sequence witnessing that value. $\endgroup$ – Yuval Filmus Feb 14 at 8:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.