Problem. Our goal is to buy and sell a given stock with maximum profit, assuming

Question

Problem. Our goal is to buy and sell a given stock with maximum profit, assuming (not quite realistically) that we are able to predict the future. To be more specific, we assume we have an array P[1..n] (n 2 2) such that for each i 1.n, Pli] is the price (0) 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 such a sequence of actions is valid; that is the BuYs and SELLs are alternating: between two BuY actions there is always a SELL action, and between two SELL actions there is always a BuY action; we cannot sell before we buy: before a SELL action there is always a BUY action:; · "cool down requirement": a SELL cannot be immediately followed by a BUY If a valid sequence has a BuY without any subsequent SELL we say that it is incomplete; otherwise it is complete. It is easy to see that an optimal valid sequence must be complete. As our running example, consider the prices In that case, an (the) optimal sequence of actions is 1 2 345 6 7 8 NONEBUY NONE SELL NONEBUY SELL NONE which will give a profit of (5-2) (3-2)-4. To solve this problem, we may try various approaches 1. (4p) An algorithm based on divide conquer. But it is not obvious how to do so: in our example, find the best valid sequence from Pl1.4] and the best valid sequence from P5.8], and then show that they can not be combined to form the best valid sequence from P[1.8] 2. (4p) The brute force approach where we examine all possible sequences (and choose the best) But this is infeasible show that the number of valid sequences is in ?(an) for some a > 1

Explanation / Answer

We have given array P[1....n] for price on different days of selling and buying for example.

and we have set sell and buy according to mention condition.

Algorithm based on divide and conquer:-1) Divide the given array in two halves in equal size.(recursively do this step until we reach single cell of an array )

2) set the buy and sell on each cell as followes while conquer the cell back to full array:-

a)left cell will be filled by buying

b)right cell will be filled by selling

c) single cell will be filled by none

do step 2 repeatedly untill we build full array

Note:- while doing step 2 if we encounter with selling comes immediate followed by buying try to remove it by replaceing their postion with given condition if we are unable to do it then set none in place of one pair of sell and buy . it will take only linear time .

Proof:- counter example that will show divide and conquer algorithm will not give optimal sequence.t

lets consider P[1...9]

divide the array:-

conquer:-

HERE we have violation so need to replace and filled none

HERE THE PROFIT IS (2+3+1)=6

But the optimal profit will be (3+8)=11

1 2 3 4 5 6 7 8 4 2 3 5 1 2 3 2

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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