Why can't use "Divide and conquer" approach for Max Product Subarray?

1
votes

We can certainly devise divide and conquer for Maximum sum subarray, but while developing divide and conquer based algorithm for maximum product subarray, I found we might need to keep the maximum & absolute maximum for both parts (and crossing products), but it seems we can devise it. I was just curios why I don't see any divide and conquer based algorithm in discussions?

Is it because since we keep the max and global max are we going towards the DP?

Any idea will be appreciated. I just want to clarify my understanding for approach. Thanks.

1
algorithmdata-structuresdivide-and-conquer
@phimuemue: This will work provided all the values are strictly positive, but if any are negative or zero then the log function is undefined. - j_random_hacker
I don't know why divide and conquer approaches to the max-product subarray problem aren't discussed, but it might have something to do with the fact that (a) the problem is very similar to the sum version and (b) IIRC the D&C approach is O(n log n) and therefore suboptimal to Kadane's O(n) algorithm. Also as I see it you need to keep the largest and smallest (i.e. most negative) values for each subproblem. - j_random_hacker

1 Answers

0
votes

It is because every time the local maximum value that is returned by recursive function call cannot be guaranteed to a factor of global maximum. You can image in some case the global maximum can be the product of neither the local maximum nor minimum.