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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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)”