Find max product using divide and conqure in O(n) time

Question

I'm trying to create and algorithm using divide and conquer that runs in O(n) time, it needs to find the maximum product between two numbers in an array of distinct numbers that can be positive or negative. I've been trying to use findMax and findMin to solve this but I cant figure it out.

Answer 1

You have an array A, this array can be split into two subarrays B and C. The maximum product for A, is one of the following:

1. The maximum product from B
2. The maximum product from C
3. The largest positive value from B multiplied with the largest positive value from C
4. The largest negative value from B multiplied with the largest negative value from C

You have to be able to combine two subarrays in constant time:
Given max_prod_B, largest_pos_B, largest_neg_B, max_prod_C, largest_pos_C, largest_neg_C you can create (in constant time):

max_prod_A = max(max_prod_B,max_prod_C, largest_pos_B x largest_pos_C, largest_neg_B x largest_neg_C)
largest_pos_A = max(largest_pos_B,largest_pos_C)
largest_neg_A = min(largest_neg_B,largest_neg_C)

aaand ... Done.