## 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

gr81
New poster
Posts: 46
Joined: Wed Sep 26, 2012 7:52 pm

### Re: 11059 - Maximum Product

what would be the output for the following test case.

2
-1 -2

6
2 5 -1 2 -3 0

do i need to consider the -ve number, if I go with problem statement, output for 1st test case should be 0 and for 2nd test case should 10, but UVA toolkit gives different output. please suggest.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11059 - Maximum Product

Code: Select all

``````Case #1: The maximum product is 2.

Case #2: The maximum product is 60.

``````
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11059 - Maximum Product

Input:

Code: Select all

``````18
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10``````
AC output:

Code: Select all

``````Case #1: The maximum product is 1000000000000000000.

``````
Check input and AC output for thousands of problems on uDebug!

gr81
New poster
Posts: 46
Joined: Wed Sep 26, 2012 7:52 pm

### Re: 11059 - Maximum Product

thanks brian, is there any O(n) solution for that, can we solve this problem using modified Kadane algorithm...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11059 - Maximum Product

Here's one:
http://dsalgo.blogspot.com/2008/06/maxi ... oduct.html

O(n*n) is fast enough for n<=18.
Check input and AC output for thousands of problems on uDebug!

armankashef
New poster
Posts: 10
Joined: Tue Jun 05, 2012 9:33 pm

### 11059 - Maximum Product

hi
Why I getting WA

Code: Select all

``````#include <iostream>
#include <math.h>
#include <string>
#include <string.h>
#include <stdio.h>
using namespace std ;
long long f( int m[18] , int n )
{
long long i , j, t , s = 1 , mx = 0 ;
for ( i = 2 ; i < 262144 ; i++ )
{
t = 0 ;
s = 1 ;
for( j = 17 ; j >= 0 ; j-- )
{
t = ( i >> j ) - t * 2 ;
if( t )
s *= m[j] ;
}
mx = max( mx , s ) ;
}
return mx ;
}
int mat[19];
int main()
{
int n , i , j = 1 ;
while( cin >> n )
{
memset( mat , 0 , sizeof ( mat ) ) ;
for( i = 0 ; i < n ; i++ )
{
cin >> mat[i] ;
}
cout << "Case #" << j << ": The maximum product is " << f( mat , n ) << "." << endl << endl ;
j++ ;
}
return 0 ;
}
``````
help me plz

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11059 - Maximum Product

Input

Code: Select all

``````3
2 0 2``````
AC output:

Code: Select all

``````Case #1: The maximum product is 2.

``````
Check input and AC output for thousands of problems on uDebug!

armankashef
New poster
Posts: 10
Joined: Tue Jun 05, 2012 9:33 pm

### Re: 11059 - Maximum Product

what's your mean ?
( for that test case my program's output is 4 )

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11059 - Maximum Product

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.

Your code is wrong, the correct output is 2.
Check input and AC output for thousands of problems on uDebug!

armankashef
New poster
Posts: 10
Joined: Tue Jun 05, 2012 9:33 pm

### Re: 11059 - Maximum Product

Code: Select all

``remove after ac``
Last edited by armankashef on Mon Jan 14, 2013 11:57 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11059 - Maximum Product

input

Code: Select all

``````18
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10``````
AC output:

Code: Select all

``````Case #1: The maximum product is 1000000000000000000.

``````
Check input and AC output for thousands of problems on uDebug!

armankashef
New poster
Posts: 10
Joined: Tue Jun 05, 2012 9:33 pm

### Re: 11059 - Maximum Product

Thank you
accepted

Nut_Boltu
New poster
Posts: 10
Joined: Wed Dec 12, 2012 7:47 pm

### Re: 11059 - Maximum Product

I m getting WA. plz Help.

Code: Select all

``````#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
long long  n,product,arr[25],MaxP;
int count=1;
while(cin>>n)
{
for(int i=0;i<n;i++) cin>>arr[i];

MaxP=0;
for(int i=0;i<n;i++)
{

for(int j=i;j<n;j++)
{
product = 1;
for(int k=i;k<=j;k++)
{
product*=arr[k];
if(product>MaxP) MaxP = product;
}

}

}

cout<<"Case #"<<count++<<": The maximum product is "<<MaxP<<"."<<endl;

}
return 0;
}

``````

Nut_Boltu
New poster
Posts: 10
Joined: Wed Dec 12, 2012 7:47 pm

### 11059 - Maximum Product

Why m i getting WA? plz anyone reply.

Code: Select all

``````#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
long long  n,product,arr[25],MaxP;
int count=1;
while(cin>>n)
{
for(int i=0;i<n;i++) cin>>arr[i];

MaxP=0;
for(int i=0;i<n;i++)
{

for(int j=i;j<n;j++)
{
product = 1;
for(int k=i;k<=j;k++)
{
product*=arr[k];
if(product>MaxP) MaxP = product;
}

}

}

cout<<"Case #"<<count++<<": The maximum product is "<<MaxP<<"."<<endl;

}
return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11059 - Maximum Product

After each test case you must print a blank line.
Check input and AC output for thousands of problems on uDebug!