11059 - Maximum Product

[dipaly]

thanks ....... ac now

[turcse143]

here my sample input & output i got WA
INPUT:
3
1 0 2

4
5 -9 -7 -8

2
1 0

2
-1 0

6
4 8 0 -9 6 -1

5
-8 -8 -7 5 1

2
0 0

1
0

1
-1

3
2 0 2

2
-1 1

3
-9 -7 -8

12
4 5 5 3 0 7 -3 0 10 2 4 -1

3
-1 0 -1

OUTPUT:

Case #1: The maximum product is 2.

Case #2: The maximum product is 315.

Case #3: The maximum product is 1.

Case #4: The maximum product is 0.

Case #5: The maximum product is 54.

Case #6: The maximum product is 280.

Case #7: The maximum product is 0.

Case #8: The maximum product is 0.

Case #9: The maximum product is 0.

Case #10: The maximum product is 2.

Case #11: The maximum product is 1.

Case #12: The maximum product is 63.

Case #13: The maximum product is 300.

Case #14: The maximum product is 0.
Press any key to continue

I DON'T UNDERSTAND WHAT'S THE PROBLEM.
SOMEONE PLES HELP!!

[CMG]

I just tried doing this problem and I got WA as well. My program has the same output as yours for that set of input. I also submitted a program that gave -1 for case #9 but still WA.

EDIT: Ah needed to use a long to keep maximum product. Got AC now.

[turcse143]

this my code: i don't know whats the problem. i also use the long long int
here my code:

Code: Select all

  code removed after accepted

[ashis.csedu]

Turcse,
check your

Code: Select all

maxp[]

indexing. I found your code assigns uninitialized maxp[] values to c in the following code fragment -

Code: Select all

if(c<maxp[i])
	c=maxp[i];

--here verify that all your maxp's are valid or initialized earlier.

Also check the following I/O:
Sample Input:

Code: Select all

3
0 -2 3
2
0 -2

Sample output:

Code: Select all

Case #1: The maximum product is 3.

Case #2: The maximum product is 0.

[turcse143]

ashis da i check and correct but again got WA.
This my some other output. ples check it
4
0 -2 -2 3
Case #1: The maximum product is 12.
4

0 -2 3 -2
Case #2: The maximum product is 12.
4

1 -2 0 0
Case #3: The maximum product is 1.
5

0 -2 0 0 1
Case #4: The maximum product is 1.
5

0 -2 0 0 -1
Case #5: The maximum product is 0.

IS output format correct

[ashis.csedu]

turcse143,
I found your approach is somehow wrong. Consider the following samples -

Sample Input:

Code: Select all

5
1 2 -1 3 5
18
1 2 3 4 5 -1 2 2 3 4 5 7 4 2 1 0 -3

You are keeping two information - maxn[] the maximum negative values and maxp[]: the maximum positive values, right?

But you reinitialized the maxp[] in a wrong way as I found in the above two simulations.

Think of the first sample
your approach is
maxp[] = 1, 2, ******, 6, 30

You continue keeping maxp[] after getting a negative number, so this sample input fails. Keep reinitialize maxp[] correctly.

I am giving sample output for the given two inputs:

Code: Select all

Case #1: The maximum product is 15.

Case #2: The maximum product is 13440.

[turcse143]

Thanks ashis da i got AC

[Obaida]

I don't know how many times i got WA. and don't know how many time i wasted for it.
But i think I am in a wrong way and thats why I am getting WA...
Can someone specify this.

Code: Select all

Thanks Robert.

[Robert Gerbicz]

I don't know how many times i got WA. and don't know how many time i wasted for it.
But i think I am in a wrong way and thats why I am getting WA...

Your algorithm fails on:

Code: Select all

2
-1 -1

[a96374177]

Help!!!
I tried many sample input and got the correct answer.
But I still got WA.
THX~

Code: Select all

#include<iostream>
using namespace std;

long long subseq(int* seq,int number,int nz,int zero);

int main()
{
	int n,*seq,nz,*pos,count=0,zero,x;
	long long max,tmp,prod;
	while(cin>>n){
		x=n;
		++count;
		seq=new int[n];
		zero=max=nz=0;
		prod=1;
		for(int i=0; i<n; i++)
			seq[i]=-20;
		int j=-1;
		for(int i=0; i<n; i++){
			cin>>tmp;
			if(tmp==0){ 
				if(seq[j]==0) continue;
				zero++;
				nz++;
				seq[++j]=0; 
				prod=1; 
			}
			if(tmp<0){ 
				seq[++j]=tmp; 
				nz++; 
				prod=1; 
			}
			if(tmp>0){ 
				if(i==0 || prod==1) ++j;
				prod*=tmp; 
				seq[j]=prod; 
			}
		}
		for(int i=0; i<n; i++)
			if(seq[i]==-20){ x=i; break; }
		if(nz<=1 || (nz==2 && zero!=0) || !zero){
			max=subseq(seq,x,nz,zero);
			cout<<"Case #"<<count<<": The maximum product is "<<max<<"."<<endl<<endl;
			continue;
		}
		int a,b;
		max=nz=a=0;
		for(int i=0; i<x; i++){
			if(seq[i]==0 && a<i){
				tmp=subseq(&seq[a],i-a,nz,0);
				if(tmp>max) max=tmp;
				a=i+1;
				nz=0;
			}else if(seq[i]<0)
				nz++;
		}
		if(a!=x){
			tmp=subseq(&seq[a],x-a,nz,0);
			if(tmp>max) max=tmp;
		}
		cout<<"Case #"<<count<<": The maximum product is "<<max<<"."<<endl<<endl;
	}
	return 0;
}

long long subseq(int* seq,int n,int nz,int zero)
{
	int *pos;
	long long max=0,prod=1;
	if(nz<=1 || (nz==2 && zero!=0)){
		for(int i=0; i<n; i++)
			if(seq[i]>max) max=seq[i];
		return max;
	}
	pos=new int[nz];
	for(int i=0; i<nz; i++)
		pos[i]=-1;
	int j=0;
	for(int i=0; i<n; i++)
		if(seq[i]<=0) pos[j++]=i;
	prod=1;
	if(!(nz%2)){
		for(int i=0; i<n; i++)
			prod*=seq[i];
		max=prod;
		return max;
	}else{
		max=0;
		prod=1;
		for(int i=0; i<pos[nz-1]; i++)
			prod*=seq[i];
		max=prod;
		prod=1;
		for(int i=pos[0]+1; i<n; i++)
			prod*=seq[i];
		if(prod>max) max=prod;
		return max;
	}
}

[sazzadcsedu]

why the output of
4
5 -9 -7 -8
should be 315!!.
is 'nt it 360???
because it is maximum.
can annyone explain plz.

[Sedefcho]

The problem asks for the maximum positive
product involving consecutive terms. That's
why the answer is 315 in your example.

[robz84]

Hi!

I get WA and i dont know why. i ve read all the post in this topic, i ve tried all the sample input and my program generates correct output.
i tried that no newline after the last output, 1 newline after the last output, two newline....., but i still get WA. its very annoying.
my first algorithm is a simple n^2 brute force alg in java, its so simple, it's tries all the possibilites, so i dont know how i get WA..
the long maximum value in java is : 9223372036854775807 , so there is no overflow problem.
Has anyone a hint?

Code: Select all

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = null;
		StringTokenizer st = null;
		int c = 1;
		
		boolean first = true;
		
		while((line = br.readLine())!=null) {
			
			//if (!first) 					// no newline after the last output
			//	System.out.println("\n");
			//first = false;
				
			int n = Integer.parseInt(line);
			int[] S = new int[n];
			st = new StringTokenizer(br.readLine());
			br.readLine();
			
			for (int i = 0; i<n; i++)
				S[i] = Integer.parseInt(st.nextToken());
			
			long product = 1;
			long max = 0;
			
			for (int i = 0; i<n; i++) {
				for (int j = i; j<n; j++) {
					for (int k = i; k<=j; k++)
						product*=S[k];
					if (product>max)
						max = product;
					product = 1;
				}
			}
			System.out.print("Case #"+c+++": The maximum product is "+max+".");
		}
		br.close();
	}

[mf]

i ve tried all the sample input and my program generates correct output.

No it doesn't! It outputs

Code: Select all

Case #1: The maximum product is 8.Case #2: The maximum product is 20.

Notice anything wrong with it?


From http://online-judge.uva.es/p/v110/11059.html:

After each test case you must print a blank line.