We’re looking at the price of a given stock over n consecutive days, numbered i

Question

We’re looking at the price of a given stock over n consecutive days, numbered i = 1, 2, . . . , n. For each day i, we have a price p(i) per share for the stock on that day. (We’ll assume for simplicity that the price was fixed during each day.) We’d like to know: How should we choose a day i on which to buy the stock and a later day j > i on which to sell it, if we want to maximize the profit per share, p(j) p(i)? (If there is no way to make money during the n days, we
should conclude this instead.) Show an algorithm to find the optimal numbers i and j int time O(n)

Explanation / Answer

The algorithm for the given provlem to find optimal number i and j in time O(n) is given by using reverse array logic which keeps the variable called max having  maximum value that we have encountered .

Algorithm :

Step 1 : Stock[] array contains all the stocks predictions for n days [0 - n-1]

step 2: Traverse the stock[] array in reverse , The max variable will be stocks[n-1], Next go to another stock stocks[n-2], check whether it is greater than max, if it is, assign max as stocks[n-2], else if it is not, add max-stocks[j] (where j=current index) to your current profit.

step 3 : After adding each time , print the max profit you get . Print the max profit by updating days.

Pseudocode:

Iterate j from n-1 to 0
   if(stocks[j]>max)
         max = stocks[j];
   profit=profit+max-stocks[j];

The algorithm with the runtime O(n) can also be written as,

It sums up the profit in O(n) run time.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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