## 11059 - Maximum Product

Moderator: Board moderators

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong
Hello chrismoh,
Can u little bit exaplain how ur algo works in the following input
3
-9 -7 -8
May be somthing i missed or misunderstood. Plz explain. Thanks in advance.

Regards,
Chok

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Chok wrote:Hello chrismoh,
Can u little bit exaplain how ur algo works in the following input
3
-9 -7 -8
May be somthing i missed or misunderstood. Plz explain. Thanks in advance.

Regards,
Chok
At element 1: MaxPositive[1] = undef, MaxNegative[1] = -9
At element 2: MaxPositive[2] = MaxNegative[1]*(-7)=63, MaxNegative[2] = (-7)
At element 3: MaxPositive[3] = MaxNegative[2]*(-8)=56, MaxNegative = MaxPositive[2]*(-8)=-504

Therefore the biggest MaxPositive is 63.

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong
Hi Martin Macko,
Thank u very much for ur explanation. Got Accepted. Thanks again.

ErickNascimento
New poster
Posts: 6
Joined: Fri Dec 16, 2005 11:40 pm

### WA

My program has passed all the tests given in this topic, but I still got WA.
Can anyone give me more test cases with correct output. Please Help me! I am getting crazy with this problem. Thanks in advance!

This problem requires long long (64 bit) variables instead of int (32 bit) ?

Here is my code:

Code: Select all

``````
#include <stdio.h>

#define MAXN (18+10)
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))

int N;

int S[MAXN];

int MaxPosProd(){

int i;
int P[MAXN]; /* Maximum Positive Product of S[0..N-1] */
int SPPMax[MAXN]; /* SPPMax[i] = Maximum Positive Product which is Sufix of S[0..i]*/
int SPNMin[MAXN]; /* SPPMin[i] = Minimum Negative Product which is Sufix of S[0..i]*/

P[0] = ((S[0]<=0)? 0: S[0]);
SPPMax[0]=((S[0]<=0)? 0: S[0]);
SPNMin[0]=((S[0]>=0)? 0: S[0]);

for(i=1; i<N; i++){
if(S[i]==0){
P[i]=P[i-1];
SPPMax[i]=0;
SPNMin[i]=0;
}else if(S[i]>0){
if(SPPMax[i-1] != 0){
P[i]=MAX(P[i-1], SPPMax[i-1]*S[i]);
SPPMax[i]=SPPMax[i-1]*S[i];
SPNMin[i]=SPNMin[i-1]*S[i];
}else{ /*  SPPMax[i-1] == 0  */
P[i]=MAX(P[i-1], S[i]);
SPPMax[i]=S[i];
SPNMin[i]=SPNMin[i-1]*S[i];
}
}else{/* S[i] < 0  */
if(SPNMin[i-1] != 0){
P[i]=MAX(P[i-1], SPNMin[i-1]*S[i]);
SPPMax[i]=SPNMin[i-1]*S[i];
SPNMin[i]=MIN(SPPMax[i-1]*S[i], S[i]); /* detalhe:MIN */
}else{/* SPNMin[i-1] == 0 */
P[i]=P[i-1];
SPNMin[i]=MIN(SPPMax[i-1]*S[i], S[i]);
SPPMax[i]=0;
}
}

}
/*
for(i=0;i<N;i++){
printf("S[%d]=%d, P[i]=%d, SPPMax[i]=%d, SPNMin[i]=%d\n", i, S[i],  P[i], SPPMax[i], SPNMin[i]);
}
*/

return P[N-1];

}

int main(){

int k;
int iCase=1;

while(scanf("%d", &N)==1){
for(k=0; k<N; k++)
scanf("%d", &S[k]);
printf("Case #%d: The maximum product is %d.\n\n", iCase, MaxPosProd());
iCase++;
}

return 0;

}

``````

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: WA

ErickNascimento wrote:My program has passed all the tests given in this topic, but I still got WA.
Can anyone give me more test cases with correct output. Please Help me! I am getting crazy with this problem. Thanks in advance!

This problem requires long long (64 bit) variables instead of int (32 bit) ?
Try the following one:

Code: Select all

``````17
-10 -5 9 -2 -7 -3 -2 -9 4 -4 -7 8 -9 2 -6 2 -7

``````
The correct output:

Code: Select all

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

``````
Last edited by Martin Macko on Tue Aug 15, 2006 8:27 pm, edited 2 times in total.

ErickNascimento
New poster
Posts: 6
Joined: Fri Dec 16, 2005 11:40 pm

Try the following one:
Code:
17
-10 -5 9 -2 -7 -3 -2 -9 4 -4 -7 8 -9 2 -6 2 -7

The correce output:
Code:
Case #1: The maximum product is 1191778304.
Macko, my program works for your test, but I still got WA.
What's wrong? Thanks for your time.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I guess, Martin mistakenly pasted output of your program, instead of the correct output.
Answer for that test should '460886630400' (i.e. the product of all numbers in the sequence.)

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
mf wrote:I guess, Martin mistakenly pasted output of your program, instead of the correct output.
Answer for that test should '460886630400' (i.e. the product of all numbers in the sequence.)
Oops, sorry I'm going to fix it.

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
Who knows

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
It took me a while to figure out what you were referring to, w k. If I am right - yes, product of one number is the number itself, unless specified otherwise. It is one of those conventions that make life easier. It comes from another one - the product of no elements is 1.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Darko wrote:It comes from another one - the product of no elements is 1.
which, however, does not apply in this problem.

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:
i have a little missunderstanding about the problem.
please check my code. you can find it but i cant.

Code: Select all

``````

int main()
{
long int num,num1,i,max_min;
long res;
int test = 1;
while(scanf("%ld",&num)==1)
{
res = 1;
max_min = -100000;
for(i=0;i<num;i++)
{

scanf("%ld",&num1);
if(num1==0)
continue;
if(num1<0)
{
if(num1 > max_min)
max_min = num1;
}
res = res * num1;
}
if(res<0)
res /= max_min;
printf("Case #%d:",test++);
printf("The maximum product is %ld\n\n",res);
}
return 0;
}

``````

newton.................................. simply the best

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
INPUT

Code: Select all

``````3
2 0 2
``````

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am