PROBLEM LINK:Author: Kevin Atienza DIFFICULTY:Simple PREREQUISITES:Greedy PROBLEM:Given an array $A$ of length $N$, and a number $K$, find the maximum product of any $K$element subsequence, modulo $10^9 + 7$. QUICK EXPLANATION:Sort the numbers by increasing absolute value. If the product of the last $K$ numbers is nonnegative, then that's the answer. Otherwise, if all elements of $A$ are not positive, the answer is the product of the first $K$ numbers. Otherwise, you have (at most) two candidates.
If neither candidate exists, then the answer is the product of the first $K$ numbers. Otherwise, the answer is the candidate with the larger product, which is guaranteed to be positive. Also, to compare these two candidates without using big integers, you only need to compare the two numbers that you changed. EXPLANATION:The problem is easy if none of the elements of $A$ are negative: simply take the largest $K$ elements! Unfortunately, the negative numbers make this problem a little harder than that. Specifically, adding a negative number to the subsequence flips the sign of the product. But not all is lost. Suppose we sort the numbers by increasing absolute value. If the product of the $K$ numbers with the highest absolute values is not negative, then that must be the answer. Indeed, that is the largest absolute value of the product of any length$K$ subsequence, and since it's not negative, it must be the highest overall. This is exemplified by the second sample case, where the two elements with the highest absolute values are negative, yet yield the best possible product: $(5)\cdot (6) = 30$. But if their product is negative, then we need some adjustments. For example, if we can find any subsequence with a nonnegative product, then that is already better than the product of the last $K$ elements. But if a nonnegative product exists, then we can actually show that we can form an optimal subsequence by taking the last $K$ elements and replacing exactly one element! To see why, suppose we have a subsequence with the highest possible product $S$, and it differs from the last $K$ elements by at least two elements. By assumption, the product of the values in $S$ is nonnegative, while the product of the last $K$ elements is negative. Let $A_i$ and $A_j$ be two of the last $K$ elements that are not in $S$, and let $A_{i'}$ and $A_{j'}$ be two of the elements in $S$ that are not in the last $K$ elements. Then it follows that $A_{i'}, A_{j'} \le A_i, A_j$. Also,
We can repeatedly apply this until our sequence only differs from the last $K$ elements by just one element. After doing so, we will have a sequence with the highest possible product, yet only differs from the last $K$ elements by just one element. So how can we use this to find an answer? We need to know which value to replace and what value to replace it with. But since the product of the last $K$ elements is negative, we must replace some value in such a way that flips the sign of the product. It means either:
But we want the absolute value of the product to be as high as possible, so only two candidates remain:
The answer must be one of these candidates; specifically, the one with the higher product! But there are a couple of problems with this:
To handle the first problem:
To prove the second one, suppose no candidate exists. Suppose also that not all remaining elements are zero. Then we want to show that none of the elements are positive. To see why, notice that the product of the last $K$ elements are negative, so at least one negative element $A_i$, $i > NK$ exists. For the first candidate to not exist, all nonzero values $A_{j'}, j' \le NK$ must be negative too. But then for the second candidate, $j'$ exists, so for it to not exist, all elements $A_i$, $i > NK$ must be negative. This proves that none of the elements are positive! Finally, if both candidates exist, then we can't compare them directly because the products are too large. Luckily, the candidates have products that don't differ a lot from the product of the last $K$ elements. Specifically, if $P$ is the product of the last $K$ elements, then:
Which means we must do the comparison $P\cdot \frac{A_i}{A_{i'}} > P\cdot \frac{A_j}{A_{j'}}$. But here, we can cancel the $P$! Specifically, this comparison has the same result as the comparison $\frac{A_i}{A_{i'}} < \frac{A_j}{A_{j'}}$. Notice that the inequality direction changed, because $P$ is negative by assumption. Finally, by multiplying $A_{i'}A_{j'}$ to both sides, we find that that comparison has the same result as $A_iA_{j'} > A_jA_{i'}$. Notice that the inequality direction changed again, because $A_{i'}A_{j'}$ is negative. The last comparison doesn't need more than 64bit variables, so it can now be done! We can summarize the algorithm here. Note that in this algorithm, we have avoided using numbers that don't fit in 64bit variables.
When computing the product of a list of numbers, be sure to reduce intermediate values modulo $10^9 + 7$! Time Complexity:$O(N \log N)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 13 Jun '16, 21:19

can we use itertools module to solve this problem in python. answered 19 Jun '16, 08:57

In the above algorithm, there is no need to check the condition for existence of j1, because j1 will always exist. answered 18 Jun '16, 18:16

"*After learning to solve maximum sum subarray problem, it's time for you to solve the maximum product subsequence.*" Why is it mentioned in the problem? Does the author want to deviate us towards "maximum product subarray problem"?? :P I was thinking of big number multiplication, then after a few minutes I realised it's subsequence, not subarray. :D answered 18 Jun '16, 04:45

Hello, @ashish1729 and @menikhilpandey. I used the same logic . I made a separate case for all negative numbers whereby I will choose last k numbers. For a mix of negative and positive,(if k is even) I am sorting array in increasing order and putting counter i on 0 and counter j on n1. I will check whose product is greaterof elements on i and i+1 or those on j and j1. That one will be multiplied to product and its index is updated. This will continue until I choose k elements. If k is odd, I will choose rightmost element and j will be n2. same process then! I couldnot find any failing test case. Please help me. I have given a lot of time to this:( Link to my solution:https://www.codechef.com/viewsolution/10489066 answered 17 Jun '16, 15:33

can anyone help me with this:I am not able to figure out the flaw https://www.codechef.com/viewsolution/10515847 answered 16 Jun '16, 10:51

I cant understand why i am getting WA.Someone please help soln link https://www.codechef.com/viewsolution/10473467 answered 16 Jun '16, 00:20

I have been trying to reach to this problem in practice mode from last 10 hrs. Link to practice on top is not working fine, always popping out with an alert that problem is not visible now please try again later. Can you please resolve the issue @admin answered 15 Jun '16, 22:20

I am getting a WA link : https://www.codechef.com/viewsolution/10487137 My logic was: If k is odd, take a single element from the right of the sorted array, and recurse with k=k1. If k is even, take the maximum of the product of the two leftmost elements, or the product of the two rightmost elements, then recurse into k=k2 Please look into the solution and let me know the corner cases i missed. answered 15 Jun '16, 15:58
ah sorry havent read your solution but try this 4 3 2 1 if k is 3 you will choose 4 * 3 * 1 = 12 but that will not work ans will be 1 * 2 * 3 flaw in logic: assuming rightmost element to be positive
(16 Jun '16, 06:29)
Thanks Ashish i got the flaw :)
(16 Jun '16, 10:29)

I did the question using log (base 10 ) , as i thought computation with log can be easier in this question. If all the N elements are non positive , divide this in 2 subtasks: If N=K, just take product of all elements. If however , all the N elements are neither positive or negative, just a basic logic works .  Take product of first K negative integers only. Among all the above options choose the one which fetches maximum value ( this can be easily done by comparison of summation of log values ) . Apart from these , there are some corner case which can be easily handled. This is the link to by submission  Submission Hope it helps :) answered 15 Jun '16, 13:55

EXPLANATION: answered 15 Jun '16, 13:10
