0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ $[-2,-1,-3,-4,6,-5,-7]$ What is solution here? $[6]$? $\endgroup$
    – kelalaka
    Commented Oct 27, 2018 at 14:48
  • $\begingroup$ No, the solution is the product of the whole array. $\endgroup$
    – user95614
    Commented Oct 27, 2018 at 18:24
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Commented Oct 29, 2018 at 3:51

1 Answer 1

1
$\begingroup$

Yes, you can obviously solve it like that.

If you are dividing the array into two parts, than the maximal sub-array can be completely in the left half, completely in the right half, of it starts in the left and ends in the right half. The first two cases you will find using the recursive calls. For the third case, you have to do a little bit of work:

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.