11059 - Maximum Product

[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]

Code: Select all

Case #1: The maximum product is 2.

Case #2: The maximum product is 60.

[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.

[gr81]

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

[brianfry713]

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

O(n*n) is fast enough for n<=18.

[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]

Input

Code: Select all

3
2 0 2

AC output:

Code: Select all

Case #1: The maximum product is 2.

[armankashef]

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

[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.

[armankashef]

Code: Select all

remove after ac

[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.

[armankashef]

Thank you
accepted

[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]

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]

After each test case you must print a blank line.