Divide and Conquer Algorithm – Clarification Needed

algorithmsjava

I have a homework assignment for a data structure/algorithm class. The task is to take an unsorted array of size n (example: [-8, 3, 2, -3, 3, 1, -3, -5]), and we have to use a divide and conquer approach, w/ recursion, to find the subsequence with the largest product.

It is the same as this question: http://www.wou.edu/~broegb/Cs345/MaxSubsequenceSum.pdf except instead of sum, my question looks for a product.

I understand a D&C approach is desirable because it has time complexity log(n) (halving) instead of n^2 (nested loop). What I'm unclear on is: is the entire function supposed to be one recursive call? Or is it like:

  1. Divide into halves.
  2. Recursive function to find largest and smallest (bc neg * neg) products of left half
  3. Same but right half
  4. Same but for the "border" of the midpoint and left half
  5. Same but for the "border" of the midpoint and right half
  6. Compare all values

Is this done with if/else's and then recursive calls, or is it all the same recursive function with if/else's inside it? Is there a methodical way I can try to tackle this program? I feel very lost.

Best Answer

The divide and conquer algorithm has 3 steps at each level:

  1. A recursive call on the left half.
  2. A recursive call on the right half.
  3. Calculate the maximum mixed sum.

Steps 1 and 2 are recursive, they just call the function again using the new end points. Step 3 is not, it just uses the fact that the sum/product must include the border values to make only n iterations. For example, if you had [1 2 3 4 5 6] it knows a mixed sum/product must have 3 and 4, and it can just check 123, 23, 3 and 4, 45, 456, and then combine the two to get the max mixed sum/product.

Now you just compare the results from steps 1, 2, and 3 and the largest is the maximum sub-sum/product possible.

EDIT: Some simplified pseudo code:

function maxProd(array)

A = maxProd(array[first half])

B = maxProd(array[second half])

C = Calculate the maximum product that contains an element from both halves

return max(A,B,C)

Related Topic