Longest Increasing Subsequence

DSA · Advanced

Definition

LIS is the longest subsequence with strictly increasing values.

Shows how binary search speeds up DP to O(n log n).

Diagram

Flowchart

Example: Patience sorting

from bisect import bisect_left
tails = []
for x in [10, 9, 2, 5, 3, 7, 101, 18]:
    i = bisect_left(tails, x)
    if i == len(tails): tails.append(x)
    else: tails[i] = x
print(len(tails))

Output: 4

Complexity

O(n log n)

Key points

Simple DP is O(n²)
tails is not the actual sequence

Interview questions

Why replace in tails?

A smaller tail keeps more room for future elements.