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:
- Divide into halves.
- Recursive function to find largest and smallest (bc neg * neg) products of left half
- Same but right half
- Same but for the “border” of the midpoint and left half
- Same but for the “border” of the midpoint and right half
- 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.
1
The divide and conquer algorithm has 3 steps at each level:
- A recursive call on the left half.
- A recursive call on the right
half. - 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)
2