i can think of a O(n) solution for this problem......though i am using extra
space O(n)
take an extra array array b[] apart from given array a[]
where b[i] denotes the maximum product of continuous ending at i....
b[0]=a[0]
traverse the given array a[] and update b[] according as -
if(b[i-1]==0)
{
if(a[i]<=0)
b[i]=0;
else
b[i]=a[i];
}
if(b[i-1] > 0)
{
if(a[i]>0)
b[i]=a[i]*b[i-1];
else
b[i]=a[i];
}
if(b[i-1]<0)
{
if(a[i]<0)
b[i]=a[i]*b[i-1];
else
b[i]=a[i];
}
after this traverse the array b[] in O(n) to find the maximum product.....
On Wed, Jul 13, 2011 at 10:11 AM, Aakash Johari <[email protected]>wrote:
> Just take 2 arrays. MinArr, MaxArr. Where MinArr[i] is Minimum product so
> far. and MaxArr[i] is Max Product so far.
>
> For any position i,
> get MaxArr[i] = max(A[i] * MaxArr[i], A[i] * MinArr[i]);
> get MinArr[i] = max(A[i] * MaxArr[i], A[i] * MinArr[i]);
>
> you will have to take care, when first element is negative. For that, make
> MaxArr[0] = 1.
> and if positive, take MinArr[0] = 1;
>
> and when you strike with a zero, do similar things.
>
>
>
> On Tue, Jul 12, 2011 at 9:13 PM, shilpa gupta <[email protected]>wrote:
>
>> given an array of natural numbers (+ve, 0, -ve) find the maximum
>> product of continuous elements.efficient( O(nlogn) or better)solution
>> is needed.
>> thanks
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> -Aakash Johari
> (IIIT Allahabad)
>
>
>
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
