Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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)$.
