11059  Maximum Product
Moderator: Board moderators
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
11059  Maximum Product
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....
There is an O(N) algorithm, so the N could be much bigger to make people use optimal algorithm....

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
 arsalan_mousavian
 Experienced poster
 Posts: 111
 Joined: Mon Jan 09, 2006 6:19 pm
 Location: Tehran, Iran
 Contact:
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Try the following input: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
Code: Select all
1
47
1
47
Code: Select all
Case #1: The maximum product is 0.
Case #2: The maximum product is 47.
Try
The output should be 1.
Code: Select all
2
1 1
 arsalan_mousavian
 Experienced poster
 Posts: 111
 Joined: Mon Jan 09, 2006 6:19 pm
 Location: Tehran, Iran
 Contact:

 Experienced poster
 Posts: 122
 Joined: Sun Nov 13, 2005 10:25 am
 Location: Taiwan
How about the outputs of these inputs?
I got WA on this problem again....
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
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.

 Experienced poster
 Posts: 105
 Joined: Wed May 25, 2005 7:23 am
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.
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 nonzero numbers, and remove the smallest negative number if the number of negative numbers is odd.
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 nonzero numbers, and remove the smallest negative number if the number of negative numbers is odd.
I tried to write a program using your algorithm:chrismoh wrote:Consider the list as being a sequence of shorter lists that are simply separated by zeros.
We can compute the maximal product ....
Code: Select all
AC, thanks Martin Macko
Can someone explain me why?
Last edited by ytsejam on Sun Aug 06, 2006 9:53 pm, edited 1 time in total.
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Consider this change:ytsejam wrote: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?
main() wrote:......if(elem[0] > 0){
.........pos[0] = elem[0];
.........neg[0] = 0;
.........best = elem[0];
......} else {
.........pos[0] = 0;
.........neg[0] = elem[0];
.........best = 0;
......}
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
IMHO the degenerated case of a product of just one factor is perfectly legal.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