LISLongest increasing subsequence

01Why it exists

Reach for it when you see:Subsequence (gaps allowed), increasing all the way, longest chain, nesting one inside another, both dimensions have to grow, fewest deletions or moves to make it sorted, n up to 10⁵ so O(n log n) is needed.

02The core idea

The longest increasing subsequence (LIS) asks how many elements you can pick out of an array while keeping their original order and staying strictly increasing. A subsequence may have gaps, which is what separates it from the longest contiguous increasing subarray — that one takes a single scan. The natural state is dp[i] = the length of the LIS ending at nums[i]. It has to end there, because to append nums[i] to some subsequence you need to know that the subsequence's last value is smaller than it. The transition is dp[i] = 1 + max(dp[j]) over every j < i with nums[j] < nums[i], and 1 when no such j exists. An LIS can end anywhere, so the answer is max(dp), not the last cell.

The tails version switches to a different state: tails[k] = the smallest final value among all increasing subsequences of length k+1. Among subsequences of the same length, a smaller tail is easier to extend later, so each length only needs its best one. The key invariant is that tails is strictly increasing. Suppose tails[k] ≥ tails[k+1]: take the subsequence of length k+2 ending at tails[k+1]; its element number k+1 is smaller than tails[k+1] and therefore smaller than tails[k], contradicting the claim that tails[k] is the smallest tail. Since it is sorted, a new element x is placed with lower_bound, which finds the first position pos holding a value ≥ x. Then tails[pos-1] < x, so x can follow a subsequence of length pos to form one of length pos+1 ending at x; and since x ≤ tails[pos], overwriting tails[pos] with x can only help, leaving every other cell untouched. When pos equals the length of tails you append instead, and the LIS grows by one. The method is also known as patience sorting, where each cell of tails is the top card of a pile.

Complexity. The O(n²) version has to scan everything before i whatever the data looks like, so best and worst case are both Θ(n²), in O(n) space. The tails version does one binary search per element over an array no longer than the LIS length L, which makes it O(n log L): on strictly decreasing data L = 1 and it is close to O(n); on strictly increasing data L = n, the worst case of O(n log n). Space is O(L) for tails, plus an O(n) parent array if you want the sequence back, O(n) in total. At n = 10⁵, n² is 10¹⁰ and only n log n, about 1.7 × 10⁶, is remotely feasible.

Common pitfalls. tails is not the LIS itself — its cells can come from different subsequences, and only its length is meaningful; to get a sequence out, store indices and record what each element follows. Strict or non-strict: strictly increasing uses lower_bound (bisect_left), while non-decreasing, where equal values are allowed, uses upper_bound (bisect_right); get it wrong and duplicates are over- or under-counted. Two dimensions need the sort first, with the second dimension descending when the first ties, or envelopes of equal width will look as though they nest. Counting how many distinct LIS exist is beyond tails; go back to the O(n²) DP and keep a separate count[i]. Next to the neighbouring lessons: in 1-D DP the state depends on only the last item or two, whereas the LIS dp[i] depends on everything before it, which is what makes it O(n²); LCS is an O(mn) table over two sequences, and LIS is in fact the LCS of nums with a sorted, deduplicated copy of nums — conversely, when one of the two sequences has no repeated elements, LCS can be turned into an LIS and solved in O(n log n).

03The algorithm

1. 1Work out whether the problem wants a subsequence (gaps allowed) or a contiguous subarray, and whether it is strictly increasing or allows equal values. If it is two-dimensional (envelopes, boxes), first sort by the first dimension ascending and by the second descending on ties, then keep only the second.
2. 2For n up to a few thousand, or when you need a count: dp = [1] * n, then for each i scan every j < i and set dp[i] = max(dp[i], dp[j] + 1) whenever nums[j] < nums[i]. The answer is max(dp).
3. 3For O(n log n): start with an empty tails and, for each x, compute pos = lower_bound(tails, x) (use upper_bound if equal values are allowed).
4. 4Append when pos == len(tails), otherwise set tails[pos] = x. Once everything is processed, len(tails) is the length of the LIS.
5. 5If you need the sequence itself: store indices in tails, record parent[i] = tails[pos-1] while processing element i (−1 when pos is 0), then walk back from the last slot of tails along parent and reverse.

04Interactive demo

Eight days of stock prices, [3, 1, 4, 1, 5, 9, 2, 6], with both modes running on the same data. "O(n²) DP table" fills in dp[i] cell by cell: blue is the current i, green are the smaller values j that it could follow, and yellow is whichever of them has the largest dp. Notice that the 1 at i = 3 cannot attach to the earlier 1, because the sequence has to be strictly increasing. The final step highlights 3 → 4 → 5 → 9 in green, recovered by following the predecessors back. "O(n log n) tails" binary-searches for each element first (yellow marks the position found, and a yellow dashed + means it goes on the end), then overwrites or appends (blue). Look at the last step: tails is [1, 2, 5, 6], and the length of 4 is correct, but the indices it came from — 3, 6, 4, 7 — are not increasing, so it is not an actual subsequence.

05Code

Four functions: the O(n²) DP (the Python version also rebuilds the sequence through prev, while the C++ version returns only the length), the tails version that just returns the length, an O(n log n) version that stores indices plus parent to rebuild the sequence, and the sort that collapses Russian Doll Envelopes into a one-dimensional LIS. Both approaches are here because the O(n²) version is easier to follow and extends to counting, while only the tails version copes with large inputs. The examples use the same eight days of prices as the interactive demo; the two versions rebuild different subsequences, but of the same length.

from bisect import bisect_left


def lis_dp(nums):
    """O(n²): dp[i] = length of the LIS ending at nums[i]; also reconstructs one LIS"""
    n = len(nums)
    if n == 0:
        return []
    dp = [1] * n
    prev = [-1] * n                          # prev[i]: which index nums[i] is appended after
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
    k = max(range(n), key=dp.__getitem__)    # the answer is the maximum of dp, not necessarily dp[-1]
    seq = []
    while k != -1:
        seq.append(nums[k])
        k = prev[k]
    return seq[::-1]


def lis_length(nums):
    """O(n log n): tails[k] = the smallest tail among increasing subsequences of length k+1"""
    tails = []
    for x in nums:
        pos = bisect_left(tails, x)          # first entry >= x; use bisect_right for non-decreasing
        if pos == len(tails):
            tails.append(x)                  # larger than every tail: the LIS gets longer
        else:
            tails[pos] = x                   # same length, smaller tail
    return len(tails)


def lis_sequence(nums):
    """O(n log n) with reconstruction: tails holds indices, plus a predecessor per element"""
    tails = []                               # tails[k]: index in nums of the smallest tail of length k+1
    parent = [-1] * len(nums)
    for i, x in enumerate(nums):
        pos = bisect_left(tails, x, key=lambda t: nums[t])  # the key parameter needs Python 3.10+
        if pos > 0:
            parent[i] = tails[pos - 1]       # appended after the smallest tail of length pos
        if pos == len(tails):
            tails.append(i)
        else:
            tails[pos] = i
    seq, k = [], tails[-1] if tails else -1
    while k != -1:
        seq.append(nums[k])
        k = parent[k]
    return seq[::-1]


def max_envelopes(envelopes):
    """Russian doll envelopes: widths ascending, heights descending on ties, then LIS on the heights"""
    order = sorted(envelopes, key=lambda e: (e[0], -e[1]))
    return lis_length([h for _, h in order])


if __name__ == "__main__":
    prices = [3, 1, 4, 1, 5, 9, 2, 6]
    print(lis_dp(prices))          # [3, 4, 5, 9]
    print(lis_length(prices))      # 4
    print(lis_sequence(prices))    # [1, 4, 5, 6] (a different LIS of the same length)
    print(max_envelopes([[5, 4], [6, 4], [6, 7], [2, 3]]))  # 3
    shelf = [4, 2, 5, 1, 3, 6]     # the call numbers on the shelf
    print(len(shelf) - lis_length(shelf))  # 3 (at least 3 books have to move)

06Practice

• LeetCode 300Longest Increasing Subsequence (write both versions once)Medium
• LeetCode 334Increasing Triplet Subsequence (a tails array capped at length 3)Medium
• LeetCode 673Number of Longest Increasing Subsequence (O(n²) DP plus counting)Medium
• LeetCode 354Russian Doll Envelopes (sorting collapses it to one dimension)Hard
• LeetCode 1964Find the Longest Valid Obstacle Course at Each Position (non-decreasing, so upper_bound)Hard
• LeetCode 1713Minimum Operations to Make a Subsequence (LCS turned into LIS)Hard