Longest Increasing Subsequence

Free with account Updated Nov 19, 2026 · 4 min read
On this page

    Problem statement

    Given a list of integers, return the length of its longest strictly increasing subsequence. A subsequence keeps the original order but may skip any elements; it does not need to be contiguous.

    This one is asked for two reasons: the O(n²) DP is a clean first DP, and the O(n log n) "tails + binary search" version separates good answers from strong ones. Original problem: LeetCode 300.

    Example

    One longest increasing subsequence of 3, 1, 8, 2, 5, 9, 4, 7 is 1, 2, 5, 7, so the answer is 4.
    One longest increasing subsequence of 3, 1, 8, 2, 5, 9, 4, 7 is 1, 2, 5, 7, so the answer is 4.
    Input:  [3, 1, 8, 2, 5, 9, 4, 7]
    Output: 4          # e.g. 1, 2, 5, 7
    Input:  [5, 5, 5]
    Output: 1          # strictly increasing, so equal values don't chain

    Constraints (assumed)

    • 1 ≤ n ≤ 2,500 (enough for O(n²); the follow-up asks for O(n log n)).
    • −10⁴ ≤ value ≤ 10⁴.

    What this question tests

    • Defining a DP state that ends at index i, which is what makes the recurrence simple.
    • Knowing (and explaining) the patience-sorting / tails improvement to O(n log n).
    • Getting strict vs non-strict right in the binary search.

    Questions to ask first

    1. Strictly increasing or non-decreasing? (Here: strict.) This decides bisect_left vs bisect_right.
    2. Length only, or the subsequence itself? Rebuilding it needs extra bookkeeping.
    3. How large is n? O(n²) is fine for a few thousand, not for a million.
    4. Empty input? Return 0.