Problem 5 Faster Price Run

This question develops the challenge problem from Price Run in Homework 3. In the problem you are given a list of closing stock ticker prices p1, p2, . . . , pn and the goal is to find the length of the longest (not necessarily consecutive) streak of prices that increase or stays the same. For example, given the prices 2, 5, 2, 6, 3, 3, 6, 7, 4, 5, there is the streak 2, 5, 6, 6, 7 of prices that increase or stay the same, but an even longer streak is 2, 2, 3, 3, 4, 5. Thus, the answer is 6.

One solution to this problem is to define a variable longi to be the length of the longest sub-sequence of prices that only increase or stay the same in height among the prices from p1, . . . , pi that ends with price pi .

First observe that long1 = 1. Next, note that if pi is larger than pj , then i can be added to the longest subsequence of prices that ended at j to form a longer subsequence. In other words, if pi ≥ pj , then one can form a sequence of length 1 + longj by considering ..., pj , pi where the ... represents the prices in the longest sequence that ends at price j. Thus we have

Finally, the longest overall sub-sequence is simply maxn i=1 {longi}. Computing each value longi takes O(n). There are n such values; thus, the overall running time is Θ(n 2 ) because the last step of finding the max takes Θ(n).

In this problem you will improve the solution to an O(n log n) time algorithm. Notice that line 3 uses a linear scan requiring Θ(i) steps to find the price that is smaller than pi and currently has the largest length.

We can improve our solution by maintaining a slightly different DP variable that allows us to use binary search instead of linear scan for this step. The idea is to consider the variable fasti which maintains “the index of the smallest price that ends a sequence of length i that increases or stays the same." If no such value exists, we define it to be ∞. To compute, it is index k which has the smallest pk among the set of indicies

{k such that k > fasti−1 ∧ pk > pfasti−1 }

(a) In a problem of size 1, what is fast1 ?

(b) Assuming we have computed fasti for i = 0, . . . , j, explain in words how to update the values given the next price pj+1.

(c) Provide pseudo-code for an algorithm that uses this insight to solve the Price Run problem in Θ(n log n) time. Justify the running-time.

(d) (Why we maintain indicies?) Assuming we have computed this fasti variable for all i = 1, . . . , n, and we know that the longest price run is j, how can we print the prices which correspond to this longest run?