11059 - Maximum Product

[Martin Macko]

Why the maximal N is so small? Just 18 as written in the problem statement...

There is an O(N) algorithm, so the N could be much bigger to make people use optimal algorithm....

[Adrian Kuegel]

I guess the low limit was used because otherwise the result would not fit into 64-bit integer.

[Martin Macko]

I guess the low limit was used because otherwise the result would not fit into 64-bit integer.

Oh right... that's could be the point... I didn't notice it

[arsalan_mousavian]

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

[Martin Macko]

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

Try the following input:

Code: Select all

1
-47

1
47

The correct answer is:

Code: Select all

Case #1: The maximum product is 0.

Case #2: The maximum product is 47.

[mf]

Try

Code: Select all

2
-1 1

The output should be 1.

[arsalan_mousavian]

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

NOW I GOT ACCEPTED , THANKS A LOT

[Wei-Ming Chen]

How about the outputs of these inputs?

Code: Select all

3
1 0 2

4
5 -9 -7 -8

2
1 0

2
-1 0

6
4 8 0 -9 6 -1

5
-8 -8 -7 5 1

2
0 0

1
0

1
-1

I got WA on this problem again....

[mamun]

Output:

Code: Select all

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.

[temper_3243]

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.

[chrismoh]

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.

[ytsejam]

Consider the list as being a sequence of shorter lists that are simply separated by zeros.

We can compute the maximal product ....

I tried to write a program using your algorithm:

Code: Select all

AC, thanks Martin Macko

I also tried the test cases in this thread and the prog give the right answer, but I submitted it and got WA
Can someone explain me why?

[Martin Macko]

I tried to write a program using your algorithm:

I also tried the test cases in this thread and the prog give the right answer, but I submitted it and got WA
Can someone explain me why?

Consider this change:

......if(elem[0] > 0){
.........pos[0] = elem[0];
.........neg[0] = 0;
.........best = elem[0];
......} else {
.........pos[0] = 0;
.........neg[0] = -elem[0];
.........best = 0;
......}

[w k]

Try
Code:
2
-1 1


The output should be 1.

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

[Martin Macko]

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.