Longest rising streak hidden inside a price series

Question

You have a list of daily closing prices. You want the length of the longest strictly increasing subsequence, a set of days (not necessarily consecutive) whose prices keep rising. This is a rough proxy for "how long could a patient trend-follower have kept adding on strength."

prices = [4, 2, 6, 3, 7, 5, 8]
-> 4        # e.g. 2, 3, 5, 8  (or 2, 6, 7, 8)

Return the length of the longest strictly increasing subsequence in O(n log n) time. The obvious pairwise dynamic program is O(n^2); the faster version keeps a clever running structure.

Accepted Answer

The trick ("patience sorting") keeps an array tails, where tails[k] is the smallest possible ending value of any increasing subsequence of length k+1 found so far. For each new price, binary-search for the first tail that is greater than or equal to it: if none exists, this price extends the longest run (append it); otherwise it replaces that tail, because a smaller ending value keeps more future options open. The length of tails is the answer. Using bisectleft enforces strictly increasing (equal values overwrite rather than extend). tails is not itself a valid subsequence, only its length is…

Longest rising streak hidden inside a price series

Your answer

More Coding questions