i 've got many WA on this problem , i have used long long to store the result
and multiply it by each input , whenever the result is greater than zero , i compare it with max , and finaly print it , where is my mistake
arsalan_mousavian wrote:i 've got many WA on this problem , i have used long long to store the result
and multiply it by each input , whenever the result is greater than zero , i compare it with max , and finaly print it , where is my mistake
thanks mf , i'll check my code soon , my program doesn't give the right answer to your Input, but my program gives the right output for martin macko's IO
Case #1: The maximum product is 2.
Case #2: The maximum product is 315.
Case #3: The maximum product is 1.
Case #4: The maximum product is 0.
Case #5: The maximum product is 54.
Case #6: The maximum product is 280.
Case #7: The maximum product is 0.
Case #8: The maximum product is 0.
Case #9: The maximum product is 0.
1) what is the o(n) algorithm for this problem. please describe it.
2) What if they say maximum product of any elements. Then what is the complexity. Can anyone throw some light on it. My approach is sort it.
Compare the number of "negative numbers" , check if any zeros (remove them), product of positive number. if negative numbers are odd (2n +1) multiply first 2n negative and the other positive product. Can anyone tell me if it is right , if not multiply negative product * positive product.
I used o(n^2) algo.
i used unsigned long long and flag to keep track of sign. it got accepted.
Consider the list as being a sequence of shorter lists that are simply separated by zeros.
We can compute the maximal product of each list in linear time by simply going through all numbers sequentially and storing the maximum (in terms of absolute value) positive and negative products that can be obtained by ending at the current list element ( as you iterate through the list ).
e.g. for sequence 1 -2 4 -3 -1
At element 1: Max positive = 1, max negative = undefined
At element 2: Max positive = undefined, max negative = -2
At element 3: Max positive = 4, max negative = -8
At element 4: Max positive = 24, max negative = -12
At element 5: Max positive = 12, max negative = -24
So overall the answer is the highest max positive = 24 (there can be no max positive ever if there is only one negative element in the list - and this case can be handled easily)
Clearly the max positive and max negative can be obtained from previous elements.
Product of any elements is simple. No sorting needed (because that is O(n log n) time). But the rest of your algorithm is correct. You can just multiply all non-zero numbers, and remove the smallest negative number if the number of negative numbers is odd.
I've doubts whether this is correct. In accordance to the problem wording we've to find the maximum positive product. In the quoted case the only product we can obtain is -1 so the correct output should be 0!
w k wrote:
I've doubts whether this is correct. In accordance to the problem wording we've to find the maximum positive product. In the quoted case the only product we can obtain is -1 so the correct output should be 0!
Wojciech
IMHO the degenerated case of a product of just one factor is perfectly legal.