11059 - Maximum Product

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

Post by Chok »

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)

Post by Martin Macko »

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

Post by Chok »

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

Post by ErickNascimento »

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

Post by Martin Macko »

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

Post by ErickNascimento »


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:

Post by mf »

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)

Post by Martin Macko »

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 :oops: I'm going to fix it.

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

Post by w k »

Who knows :-?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

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)

Post by Martin Macko »

Darko wrote:It comes from another one - the product of no elements is 1.
which, however, does not apply in this problem. :wink:

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton »

i have a little missunderstanding about the problem.
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

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

Post by rio »

INPUT

Code: Select all

3
2 0 2
The answer should be 2, but your code outputs 4.

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton »

why and how 2?
pls

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

Post by rio »

The problem statements say:
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
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.

Post Reply

Return to “Volume 110 (11000-11099)”