## 11059 - Maximum Product

Moderator: Board moderators

dipaly
New poster
Posts: 20
Joined: Tue Sep 19, 2006 6:18 pm
Contact:

### :)

thanks ....... ac now
everything is so hard to me

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm

### 11059 - Maximum Product 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
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...
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
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm

### 11059, WA,help ples,

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
``````
Last edited by turcse143 on Sun Dec 16, 2007 5:47 pm, edited 1 time in total.

ashis.csedu
New poster
Posts: 12
Joined: Sat Aug 18, 2007 11:09 pm
Location: CSE, University of Dhaka
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
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm

### WA again help ples!!!!!!!!

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
New poster
Posts: 12
Joined: Sat Aug 18, 2007 11:09 pm
Location: CSE, University of Dhaka
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
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
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Thanks ashis da i got AC

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 11059 - Maximum Product

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.``
Last edited by Obaida on Tue May 27, 2008 10:34 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: 11059 - Maximum Product

Obaida wrote: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...

Code: Select all

``````2
-1 -1
``````

a96374177
New poster
Posts: 1
Joined: Sat Aug 16, 2008 8:55 am

### Re: 11059 - Maximum Product

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+1; i<n; i++)
prod*=seq[i];
if(prod>max) max=prod;
return max;
}
}
``````

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### WA?11059 - Maximum Product

why the output of
4
5 -9 -7 -8
should be 315!!.
is 'nt it 360???
because it is maximum.
can annyone explain plz.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### Re: 11059 - Maximum Product

The problem asks for the maximum positive
product involving consecutive terms
. That's

robz84
New poster
Posts: 3
Joined: Thu Aug 06, 2009 8:28 pm
Location: Hungary

### Re: 11059 - Maximum Product

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 {

String line = null;
StringTokenizer st = null;
int c = 1;

boolean first = true;

//if (!first) 					// no newline after the last output
//	System.out.println("\n");
//first = false;

int n = Integer.parseInt(line);
int[] S = new int[n];

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 11059 - Maximum Product

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.