What Is the Longest Increasing Subsequence?

The Longest Increasing Subsequence (LIS) finds the length of the longest order-preserving subsequence whose values strictly increase. For example, the LIS of [10, 9, 2, 5, 3, 7, 101, 18] is [2, 3, 7, 101], length 4 (it need not be contiguous).

The one-line idea: "track the longest increasing run ending at each value." Naively it's O(n²); cleverly it's O(n log n).

Approach 1: O(n²) DP

dp[i] = the LIS length ending at the i-th element.

dp[i] = max(dp[j] + 1) (for j < i with arr[j] < arr[i])

Looking at all earlier elements per i makes it O(n²). It's intuitive and easy to reconstruct the LIS from.

Approach 2: O(n log n) — tails + Binary Search

tails[k] = the smallest possible last value of an increasing subsequence of length k+1.

This tails is always increasing, enabling binary search. For a new value x:

•binary search for the first position in tails that is ≥ x and replace it with x.
•if no such position exists (x is largest), append x to tails.

At the end, the length of tails is the LIS length. The key intuition: keeping the smallest possible last value lets you extend with more values later.

How It Works (O(n log n))

Step 1. Start with an empty tails array.

Step 2. For each element x, binary search for where x belongs in tails.

Step 3. Replace at that position, or append if it's at the end.

Step 4. After processing all elements, the length of tails is the answer.

The AlgoNote visualization shows which tails slot each new value replaces or extends, step by step.

Time and Space Complexity

Approach	Time	Space
DP	O(n²)	O(n)
tails + binary search	O(n log n)	O(n)

Walking Through an Example

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

•tails evolves: [10] → [9] → [2] → [2,5] → [2,3] → [2,3,7] → [2,3,7,101] → [2,3,7,18]
•final tails length 4 → LIS length 4

Common Mistakes

•Mistaking tails for the actual LIS: tails gives only the correct length. Reconstructing the sequence needs separate tracking (recording indices).
•Definition of increasing: strict increase uses lower_bound; allowing non-decreasing uses upper_bound.
•Binary-search boundary: a wrong replacement position throws off the length.

See It in Action on AlgoNote

Watch which position of the tails array gets replaced or extended as each new value arrives, step by step on AlgoNote.

Try the LIS Visualization →