Longest Increasing Subsequence

Given a sequence of daily prices, what is the longest stretch of days (not necessarily consecutive) where the price strictly increased each time you sampled it? That's the longest increasing subsequence (LIS) problem, and it's a good test of whether you can spot a hidden binary search inside a problem that looks like plain dynamic programming.

The idea: O(n²) DP, then a smarter O(n log n)

The direct DP: let $dp[i]$ be the length of the longest increasing subsequence ending exactly at index $i$. For each $i$, look back at every earlier index $j < i$ where $\text{nums}[j] < \text{nums}[i]$, and take the best chain that ends there, plus one:

$$dp[i] = 1 + \max_{j < i,\ \text{nums}[j] < \text{nums}[i]} dp[j]$$

with $dp[i] = 1$ if no such $j$ exists (the element alone is a subsequence of length 1). The answer is $\max_i dp[i]$. This is $O(n^2)$ — for each $i$, scan all earlier $j$.

The faster method keeps an auxiliary array tails, where tails[k] is the smallest possible tail value of any increasing subsequence of length $k+1$ found so far. For each new number, binary-search tails for the leftmost position it can occupy (the first tail $\ge$ the number) and overwrite that slot, or append if the number is larger than every tail. The length of tails at the end is the LIS length. This works because keeping the tail of each length as small as possible only ever helps future extensions — never hurts — so tails is always sorted and a binary search on it is always valid, giving $O(n \log n)$.

Worked example: [10, 9, 2, 5, 3, 7, 101, 18] with the fast method

Start tails = []. 10 → append, tails=[10]. 9 → binary search finds position 0 (first $\ge 9$), overwrite, tails=[9]. 2 → overwrite position 0, tails=[2]. 5 → larger than all, append, tails=[2,5]. 3 → binary search finds position 1 (first $\ge 3$ is 5), overwrite, tails=[2,3]. 7 → append, tails=[2,3,7]. 101 → append, tails=[2,3,7,101]. 18 → binary search finds position 3 (first $\ge 18$ is 101), overwrite, tails=[2,3,7,18]. Final length 4, matching the true LIS 2,3,7,18 (or 2,3,7,101).

import bisect
def lis_length(nums):                    # O(n log n)
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Where it shows up

Interview staples: LIS itself, Russian doll envelopes (2D LIS via sort-then-1D-LIS), and "maximum length of pair chain." On a desk, LIS-style reasoning identifies the longest stretch of consistently improving performance metrics in a noisy series, and the same binary-search-on-tails pattern shows up whenever you need the length of the longest monotonic run without recomputing from scratch on every new data point.