11059 - Maximum Product

[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]

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]

Hi Martin Macko,
Thank u very much for ur explanation. Got Accepted. Thanks again.

[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]

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.

[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]

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]

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]

Who knows

[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]

It comes from another one - the product of no elements is 1.

which, however, does not apply in this problem.

[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]

INPUT

Code: Select all

3
2 0 2

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

[newton]

why and how 2?
pls

[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.