Problem $7.$ 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 wr

ite 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