Longest increasing subsequence of a price series

You get a series of financial values in time order: recorded prices, or monthly net profits, which may be zero or negative. Return the largest number of values you can pick, keeping their order, so that the picked values strictly increase.

Interface

Unless you agree on a different interface with the interviewer, assume:

• longest_increasing(prices: list[int]) -> int — the length of the longest strictly increasing subsequence; 0 for an empty list.

Example

longest_increasing([10, 9, 2, 5, 3, 7, 101, 18])  -> 4    # e.g. 2, 3, 7, 18
longest_increasing([-3, -1, 0, 0, 2])             -> 4    # the two zeros can't both count
longest_increasing([5, 5, 5])                     -> 1
longest_increasing([])                            -> 0

Constraints

• Up to 10^5 values; values fit in a 32-bit signed integer and may be negative.
• Strictly increasing: equal values can't sit next to each other in the subsequence.

Clarifying questions

• Strictly increasing, or non-decreasing?
• Is the length enough, or do you want one subsequence too?
• How long can the series be? Is O(n^2) acceptable?
• Can the input be empty?

What a strong answer covers

• The O(n^2) dynamic program first: best[i] is the longest increasing subsequence ending at i.
• The O(n log n) version: keep tails[k], the smallest last value of any increasing subsequence of length k + 1, and place each value with a binary search (bisect_left for strict, bisect_right for non-decreasing).
• Why tails is not itself a valid subsequence; only its length is meaningful.
• Tests with duplicates, negatives, strictly decreasing input and a single value.

Follow-ups

• Return one longest subsequence by keeping a parent index per value.
• Count how many longest subsequences there are.
• The longest run of consecutive increases (a subarray, not a subsequence).