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

Post by gr81 » Mon Dec 10, 2012 12:44 pm

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

Post by brianfry713 » Mon Dec 10, 2012 10:08 pm

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

Post by brianfry713 » Mon Dec 10, 2012 10:12 pm

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

Post by gr81 » Tue Dec 11, 2012 7:08 am

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

Post by brianfry713 » Tue Dec 11, 2012 11:03 pm

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

Post by armankashef » Thu Jan 10, 2013 12:04 am

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

Post by brianfry713 » Thu Jan 10, 2013 11:06 pm

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

Post by armankashef » Fri Jan 11, 2013 11:17 pm

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

Post by brianfry713 » Sat Jan 12, 2013 6:21 pm

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

Post by armankashef » Sun Jan 13, 2013 4:07 pm

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

Post by brianfry713 » Sun Jan 13, 2013 9:49 pm

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

Post by armankashef » Mon Jan 14, 2013 11:16 am

Thank you
accepted

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

Re: 11059 - Maximum Product

Post by Nut_Boltu » Sun Mar 17, 2013 6:55 am

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

Post by Nut_Boltu » Tue Mar 19, 2013 7:12 pm

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

Post by brianfry713 » Tue Mar 19, 2013 8:30 pm

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

Post Reply

Return to “Volume 110 (11000-11099)”