Given an array A of length n$,$ and two indices i and j with i $$ j$,$ define Prod$($A$,$ i$,$ j$)$ as the product of elements from A$[$i$]$ to A$[$j$],$ i$.$e$.,$ A$[$i$]$ A$[$i $+1]$ A$[$j$].$ If i $=$ j$,$ then Prod$($i$,$ j$)=$ A$[$i$].$ For example, if A $=[3,0\mathrm{.}1,5,20,4],$ then Prod$($A$,1,3)=0\mathrm{.}1520=10.$ Now, consider the following problem MaxProd$($A$)$: $$ Input: An array A of length n where all elements are positive, but may include fractional values $($e$.$g$.,$ A$[$i$]=0\mathrm{.}1$ is valid$).$ Output: The maximum possible value of Prod$($A$,$ i$,$ j$)$ for some subarray A$[$i$..$j$].$ For example, if A $=[3,0\mathrm{.}2,4,0\mathrm{.}5,1,4,0\mathrm{.}3,2],$ the maximum product is $8,$ which is achieved by the subarray $[4,0\mathrm{.}5,1,4].$ a$)$ Write pseudocode for a recursive algorithm MaxProd$($A$)$ that solves the problem in O$($n log n$)$ time. You only need to provide the pseudocode and the recurrence relation for the algorithm. $(10$ points$)$ Hint: The recurrence formula is similar to one we$$ve used before, so you don$$t need to prove that it solves to T $($n$)=$ O$($n log n$).$ Note: While there are faster, non$-$recursive algorithms for this problem, you must use a recursive algorithm for this homework. Solution. Solution to the part a$)$ goes here b$)$ Now, write pseudocode for a recursive algorithm that solves the problem in O$($n$)$ time. As in Part $1,$ provide the pseudocode and the recurrence relation for the algorithm. $(15$ points$)$ Hint: Similar to the Max Profit problem covered in class, solve a helper problem MaxProdX$($i$,$ j$),$ which gives additional information beyond just the maximum product. If you$$re confident with the O$($n$)$ algorithm, you can directly write a single solution for both Part $1$ and Part $2.$ However, if you$$re unsure, first implement the O$($n log n$)$ solution for Part $2,$ then write the separate O$($n$)$ algorithm. Solution. Solution to the part b$)$ goes here.