Our goal is to buy and sell a given stock with maximum prot, assuming (not quite realistically)that we are able to predict the future. To be more specic, we assume we have an array P[1..n] (n 2)such that for each i 1..n, P[i] is the price of the stock on day i; our goal is to compute an array A[1..n]of actions where each action is either None, Buy, or Sell. We require that after removing the Nones, thesequence of actions is of the form Buy,Sell,...Buy,Sell. Also, we require that there is a cool down day:a Sell cannot be immediately followed by a Buy.

To solve this problem we shall employ 4 tables, B[1..n] and S[1..n] and C[1..n] and M[1..n], with intendedmeaning given below: for i 1..n, B[i] is the maximum prot possible after a sequence of actions A[1]..A[i] whereA[i] = buy (thus B[1] = P[1]); for i 1..n, S[i] is the maximum prot possible after a sequence of actions A[1]..A[i] whereA[i] = sell (thus S[1] = 0); for i 1..n, C[i] is the maximum prot possible after a sequence of actions A[1]..A[i] whereA[i] = none (thus C[1] = 0); for i 1..n, M[i] is the maximum prot possible after a sequence of actions A[1]..A[i] where thereexists j 1..i such that A[j] = buy and A[k] = none for all k j + 1..i (thus M[1] = P[1]).

1. Write, and justify, the recurrences for computing (for i 2..n) the values of B[i] and S[i] andC[i] and M[i], given the values of B[i 1] and S[i 1] and C[i 1] and M[i 1].

2. Using the recurrences from step 1, write a dynamic programming algorithm to ll the arraysB[1..n] and S[1..n] and C[1..n] and M[1..n] (you may assume your language has a Max operator).

3. Augment the algorithm from step 2 so that it computes in A[1..n] an optimal action sequence,and the resulting prot.

4. Analyze the space use, and running time, of the algorithm that was developed in step 2 andaugmented in step 3.