1

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.

  • 2
    As a small aside, the run time for D&C will not be O(lg n), unless you figure out a way to solve the problem without looking at all n array elements once. (It will most likely be O(n lg n).) – Ryan M Sep 24 '14 at 16:40
1

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)

  • So it's basically: 1) Cut in half 2) Pass half A into recursive function 3) Pass half B into recursive function 4) Compare results straightforwardly. I'm assuming then, that part of the recursive function is a conditional to loop through the "edge" cases (in your example the 123 23 3, 4 45 456)? – HC_ Sep 24 '14 at 16:31
  • @HC_ The edge cases are not part of the recursion. They need to be done in addition, and the result also compared to what was returned from the recursion. Obviously, the half A side will in turn be calling the function again on A-A and A-B and also doing the edge cases for those quarters, and so on. – HamHamJ Sep 24 '14 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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