11059  Maximum Product
Moderator: Board moderators

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
At element 1: MaxPositive[1] = undef, MaxNegative[1] = 9Chok 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 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.

 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:
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..N1] */
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[i1];
SPPMax[i]=0;
SPNMin[i]=0;
}else if(S[i]>0){
if(SPPMax[i1] != 0){
P[i]=MAX(P[i1], SPPMax[i1]*S[i]);
SPPMax[i]=SPPMax[i1]*S[i];
SPNMin[i]=SPNMin[i1]*S[i];
}else{ /* SPPMax[i1] == 0 */
P[i]=MAX(P[i1], S[i]);
SPPMax[i]=S[i];
SPNMin[i]=SPNMin[i1]*S[i];
}
}else{/* S[i] < 0 */
if(SPNMin[i1] != 0){
P[i]=MAX(P[i1], SPNMin[i1]*S[i]);
SPPMax[i]=SPNMin[i1]*S[i];
SPNMin[i]=MIN(SPPMax[i1]*S[i], S[i]); /* detalhe:MIN */
}else{/* SPNMin[i1] == 0 */
P[i]=P[i1];
SPNMin[i]=MIN(SPPMax[i1]*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[N1];
}
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;
}

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: WA
Try the following one: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) ?
Code: Select all
17
10 5 9 2 7 3 2 9 4 4 7 8 9 2 6 2 7
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.

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

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

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

 Experienced poster
 Posts: 162
 Joined: Thu Jul 13, 2006 7:07 am
 Location: Campus Area. Dhaka.Bangladesh
 Contact:
i have a little missunderstanding about the problem.
please check my code. you can find it but i cant.
so please help me
newton.................................. simply the best
please check my code. you can find it but i cant.
so please help me
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
INPUT
The answer should be 2, but your code outputs 4.
Code: Select all
3
2 0 2
The problem statements say:
Consecutive terms mean { Si , Si+1, Si+2, .., Si+k } (1 <= i, i + k <= n, k >= 0), and its product menas Si * Si+1 * Si+2 * ... * Si+k.Given a sequence of integers S = {S1, S2, ..., Sn}, you should determine what is the value of the maximum positive product involving consecutive terms of S. If you cannot find a positive sequence, you should consider 0 as the value of the maximum product