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....
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I guess the low limit was used because otherwise the result would not fit into 64-bit integer.
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Adrian Kuegel wrote: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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
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
In being unlucky I have the record.
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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
Try the following input:

Code: Select all

``````1
-47

1
47

``````

Code: Select all

``````Case #1: The maximum product is 0.

Case #2: The maximum product is 47.

``````
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Try

Code: Select all

``````2
-1 1
``````
The output should be 1.
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
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
In being unlucky I have the record.
Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
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
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.
chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
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
New poster
Posts: 3
Joined: Tue Aug 01, 2006 5:27 pm
chrismoh wrote: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?
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)
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?
Consider this change:
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;
......}
w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
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
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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.