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