AlgoInsight

Q&A

The longest increasing subsequence problem

By AlgoInsight Team2026-06-07algorithmsarrays

Overview

Given an array, a subsequence is formed by deleting zero or more elements without reordering the rest. The LIS is the longest such subsequence that is strictly increasing. For [10, 9, 2, 5, 3, 7, 101, 18], one LIS is [2, 3, 7, 101] (or [2, 3, 7, 18]), length 4.

graph TD
    A["Array: 10 9 2 5 3 7 101 18"] --> B[DP O(n²): dp[i]=longest LIS ending at i]
    A --> C[Patience sorting O(n log n): tails + binary search]
    B --> D[Answer = max of dp[]]
    C --> E[Answer = length of tails array]
    style C fill:#1e1b4b,color:#fff

Approach 1: Dynamic Programming - O(n²)

Define dp[i] = length of the longest increasing subsequence ending at index i. For each i, look back at all j < i; if nums[j] < nums[i], then dp[i] can extend dp[j].

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);          // each element alone is an LIS of length 1
    int best = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        best = Math.max(best, dp[i]);
    }
    return best;
}

Time O(n²), space O(n). Intuitive and a good first answer.

Trace

For [10, 9, 2, 5, 3, 7, 101, 18]:

dp = [1, 1, 1, 2, 2, 3, 4, 4]
        10 9 2  5  3  7 101 18
max(dp) = 4

Approach 2: Patience Sorting + Binary Search - O(n log n) ⭐

Maintain a tails array where tails[k] is the smallest possible tail value of an increasing subsequence of length k+1. For each number, binary-search the position in tails where it should go:

The length of tails at the end is the LIS length.

public int lengthOfLIS(int[] nums) {
    List<Integer> tails = new ArrayList<>();
    for (int x : nums) {
        int lo = 0, hi = tails.size();
        while (lo < hi) {                 // binary search: first tail >= x
            int mid = (lo + hi) / 2;
            if (tails.get(mid) < x) lo = mid + 1;
            else hi = mid;
        }
        if (lo == tails.size()) tails.add(x);   // extend
        else tails.set(lo, x);                  // replace to keep tails small
    }
    return tails.size();
}

Time O(n log n), space O(n). Note: tails is not itself the LIS - only its length is correct. (Java's Arrays.binarySearch or Collections.binarySearch can replace the manual search.)

Why "smallest tail" works

By always keeping the smallest possible tail for each length, you maximize the chance that a future element can extend a subsequence. The array stays sorted, enabling binary search.

Reconstructing the Actual Subsequence

To return the elements (not just the length), track predecessor indices in the DP version:

int[] prev = new int[n];   // prev[i] = index of previous element in LIS ending at i
// during DP, when dp[i] is updated from j: prev[i] = j;
// then walk backwards from the index with the max dp value.

For the O(n log n) version, store, for each element, the position it occupied in tails and chain back via recorded indices.

Variants

Why This Matters in Interviews

LIS is a canonical DP problem and a frequent interview question. Interviewers want to see the O(n²) DP first (with the dp[i] = longest ending at i framing), then the O(n log n) patience-sorting + binary-search optimization, and ideally reconstruction of the actual subsequence. Explaining why keeping the smallest tail works is the senior-level insight.

Common Pitfalls

References

More answers