You are consulting for a small investment company. They give you the price of Google$$s shares over

the last n days. Let S$[1...$ n$]$ be the array of share prices, where S$[1]$ is the price of the stock on

the first day in this time period. During this window, the company wanted to buy a fixed number

of shares on some day and sell all these shares on some later day $($that is$,$ only one purchase and

one sale$).$ The company wants to know when they should have bought and when they should have

sold in order to maximize their profit. If there was no way to make money during the n days, you

should report $$Impossible$.$

For example, if n $=3$ and S $=[9,1,5],$ then you should return $$buy on day $2$ and sell on day $3.$

Your goal is to design a divide$-$and$-$conquer algorithm for this problem that runs in time O$($n log n$).$

$($a$.)(5$ points$)$ In one sentence, describe a simple algorithm for this problem that takes O$($n$2)$ time.

$($b$.)(15$ points$)$ Now design a Divide$-$and$-$Conquer algorithm and justify its correctness. Con$-$

sider two cases: $(1)$ there is an optimal solution in which the investors are holding the stock

at the end of day n$/2,$ and $(2)$ there is no such optimal solution. For each case, express the

optimal solution in terms of something you can compute on the two subarrays.

$($c$.)(5$ points$)$ Analyze the running time of your algorithm.