# Max subarray product

Is it possible to solve the max sub-array product problem using divide and conquer?

Given an integer array numbers, find the contiguous sub-array within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

• $[-2,-1,-3,-4,6,-5,-7]$ What is solution here? $$? Oct 27, 2018 at 14:48
• No, the solution is the product of the whole array. Oct 27, 2018 at 18:24
• Just in case you are not required to use divide and conquer, a solution by dynamic programming is easier to implement and probably faster to run. Oct 29, 2018 at 3:51

In that case the maximal subarray consists of two parts, a suffix from the left half of the array, and a prefix of the right half of the array. Either both products are positive, or both negative. It's obvious that you want their absolute value as big as possible, therefore you need to know the largest and smallest suffix from the left half, and the largest and smallest prefix from the right half. You can compute both in $$O(n)$$ time, which gives you the recurrence relation $$T(n) = 2 T(\frac{n}{2}) + O(n)$$ which gives you $$T(n) = O(n \log n)$$ by the master theorem.
Notice, you can also compute these values during the recursive calls, which gives you $$T(n) = 2 T(\frac{n}{2}) + O(1)$$, and this gives you the final complexity $$T(n) = O(n)$$.