Our goal is to buy and sell a given stock with maximum prot, assuming (not quite

Question

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.

Explanation / Answer

let min = minimum share price = 2 = start index

let max = maximum share price value = 500,000 = stop index

find the optimum buying days and optimum selling days

function shareMarketSellOrBuyDecision

parameters: int values[], int count

                when n is just one return ;

                start with the counter = 0

                create a solution vector called gap with the value of return value from sol[n/2 + 1

                go through the entire array of given share values

                compare the current element with the next element in the array, find the local minimum value

                compare i with n-1 if it is less then

                                compare array share values index i+1 with the previous index

                                                if that is also less, then increment the index i

once i reaches n-1, break the loop

                the array index of the local minima is stored in solution array at the index of counter

Follow a similar method to find the local maxima but compare to find the greater then value instead of the less than value

display the solution formed

stop algorithm

Run

The above will run in O(n) time in the average case

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.