1. If the array contains even number of negative numbers, then the answer is the whole array. 2. If it contains odd number of negative integers, split the array on every negative integer and calculate the product of two subarrays. Find the subarray (among all the subarrays from every split) with maximum product.
Step 2 is based on fact that the maximum product subarray can not lie between two negative numbers. (If it does, then you can consider those two numbers and get bigger product!). So it has to be between a negative integer and one of the ends of the array. Also we can calculate the product of subarray in O(1) by precalculating the cumulative products - which is O(n) (And correctly handling the overflows). So total complexity is O(n). This will work as long as there are non-zero values. ~Vishal On 4/25/07, Bootlegger <[EMAIL PROTECTED]> wrote: > > > Aye its not the same, > > I suspect the answer will have something to do with verifying the > number of negative numbers in the subarray, seen as a even number of > negative numbers will produce a positive product and an odd number of > negatives will produce a negative product. > > Bootlegger > > On 25 Apr, 13:51, "Nilesh Agrawal" <[EMAIL PROTECTED]> wrote: > > > I think the problem is same as maximum sum..since product is max. if > sum > > > is max. only thing we have to verify is that we should get even number > of > > > negative numbers in our product.. > > > > Its not the same. > > Consider the sequence: > > > > 50, -25, -25 > > > > Max. Sum subarray : 50 > > Max. Product subarray: 50, -25, -25 > > > > Nilesh > > > > -- > > And ye shall know the truth (source) and the truth shall set you free. > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
