Problem $5.[$Category: Divide and Conquer$][30$ points$]$

We will work on a very typical problem: Best time to buy and sell stock. The simplest version of this

problem is as follows:

You are given an array prices where prices$[$i$]$ is the price of a given stock on the ith day. You want to

maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to

sell that stock. And our GOAL is to maximize the profit you can achieve from this transaction, and return

that profit value. If you cannot achieve any profit, return $0.$

Example:

Input: prices $=[7,1,5,3,6,4]$

Output: $5$

Explanation: Buy on day $2($price $=1)$ and sell on day $5($price $=6),$ profit $=6-1=5.$

Note that buying on day $2($lowest price$)$ and selling on day $1($highest price$)$ is not allowed because you

must buy before you sell.

Input: prices $=[7,6,4,3,1]$

Output: $0$

Explanation: In this case, no transactions are done and the max profit $=0.$

We can of course solve the problem by brute force method, that is checking every pair of possible buy and

sell day and return the maximum profit, that will give us an algorithm running in quadratic time. But we

can actually do better that. We can solve the problem using two algorithm paradigms: divide and conquer,

dynamic programming. Here we are going to focus on divide and conquer one.

Without loss to generality, we can assume n is some number that of power of $2($if not, then we just let patch

some fakes days to make it up to n$=2$i $>$ n$,$ and the fake days will just have same price as of the nth

day$).$ The basic idea is that, the maximum profit will come from either one of the following three cases of

operations:

$1.$ both buying and selling happen during the first n

$2$ days

$2.$ both buying and selling happen during the last n

$2$ days

$3.$ buying happens during the first n

$2$ days and then selling happens during the last n

$2$ days.

In the first two cases, we just do recursive call on the procedure to find the answer. For the third case,

we can simply buy at the lowest price from the first n

$2$ days, and sell at the highest price from the last n

$2$

days, and easily get the profit for this case. Finally, we can just return the maximum value among the three

answers to get the maximum profit for the original problem. The algorithm would be as follows, please fill

the blanks and analyze the running time of the algorithm.

$6$

BestTimeBuySell$($prices$[1..$n$])$

if n $=1$ then

return $0$

end if

maxP rof it $0$

m $$ n

$2$

Aprof it $$ BestTimeBuySell$()$

Bprof it $$ BestTimeBuySell$()$

crossBuyP rice $$ min$($prices$[1..$m$])$ min$()$ function finds the minimum of the given array

crossSellP rice $$ max$()$ max$()$ function finds the maximum of the given array

Cprof it $$ crossSellP rice $$ crossBuyP rice $$ Cprofit: maximum profit of case $3$

maxP rof it $$ max$(,,)$

return maxP rof it

Analyze the running time T $($n$)$ of the algorithm:

T $($n$)=\_$T $($ n$/2)+\_$

Therefore, T $($n$)$ in