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.