What I need for this problem: 1. High level algorithm(no pseudocode, just explai

Question

What I need for this problem:

1. High level algorithm(no pseudocode, just explain how to handle this problem).

2. Subproblem definition

3. Reccurence relation

4. Proof of correctness

5. Running time for algorithm

The important parts I'm stuck on are the 1-3. 4 and 5 are less important. Thank you!

(Kleinberg and Tardos, Algorithm Design, Problem 6.7) We wish to study the price of a given stock over n consecutive days, numbered i = 1,2,...,n. For each day i, p(i) is the price per share for the stock on that day. (Assume that the price of a share does not change during each day.) 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, i.e., p(j) - p(i)? If there is no way to make money during the n days, we should calculate the profit to be zero. Describe a dynamic programming algorithm to find the optimal numbers i and j in O(n) time. Please provide a proof of correctness and running time of your algorithm.

Explanation / Answer

We can solve this as follows.

If we assume that we know the solution for the first i days. We need to use this info to calculate the solution for i+1 days.

Lets see the possible scenarios.

1. The profit increases for i+1 days => the difference between the p(i+1) and minimum price in first i days is greater than the profit in first i days.

2. profit remains the same for i+1 days => the solution for the first i days is optimal and we can neglect the p(i+1). This happens when the difference between the p(i+1) and mininmum price in i days is lesser than the profit in first i days.

3. profit decreases for i+1 days. But this cannot happen at all. We always choose the best profit.

We need to formulate this as a dynamic programming recurrence.

We keep track of Profit(i) which is maximum profit in the first i days, and min(i) which is the minimum element in i days.

Profit(i+1) = max(p(i+1)-min(i), Profit(i))

Thus we get the recurrence relation. We could have as well solved the problem for i+1 days without using the info Profit(i) and min(i). Then it would have been a O(n^2) solution.

We used a dynamic programming solution because of which we now solve the problem in O(n) time.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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