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
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;
}
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.
Macko, my program works for your test, but I still got WA.
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.
Oops, sorrymf 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.)
I'm going to fix it.
which, however, does not apply in this problem.Darko wrote:It comes from another one - the product of no elements is 1.
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;
}
Code: Select all
3
2 0 2
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