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 halfSame but right halfSame but for the border of the midpoint and left halfSame but for the border of the midpoint and right halfCompare all valuesIs 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.
Divide and Conquer Algorithm clarification needed
java;algorithms
The divide and conquer algorithm has 3 steps at each level:A recursive call on the left half. A recursive call on the righthalf.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 halvesreturn max(A,B,C)