Longest Increasing Subsequence

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1

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

Output: 4

Patience sort: tails[i] = smallest tail of IS of length i+1. Binary search for first tail ≥ num; extend or replace.

Input & Tails

Variables

i / num

—

pos

—

action

—

tails.length

—

Step Logic

Press ▶ Play or Next Step to begin.

Ready

0 / 0

Select an example and press Play.

Algorithm

tails[i] = smallest tail of IS of length i+1

For each num: binary search first tail ≥ num

Replace or extend: pos==size → append, else tails[pos]=num

Answer = tails.size()

Time

O(n log n)

Space

O(n)

Why This Works

Patience sorting: maintain pile tops. Each number goes on leftmost pile whose top ≥ it (binary search). If larger than all, new pile. Number of piles = LIS length.

How to solve Longest Increasing Subsequence

LeetCode 300 · Medium · Dynamic Programming · Pattern: 1D DP

Why the obvious approach is slow

There are 2 to the power n subsequences, so checking all of them is hopeless. Instead, remember the best answer that ends at each position.

The key idea

Let dp of i be the length of the longest increasing subsequence that ends exactly at index i. Every element alone is a subsequence of length 1. For each earlier index j with a smaller value, you can extend that subsequence by the element at i. So dp of i is 1 plus the largest such dp of j. The answer is the largest value anywhere in dp.

Remember

Define dp as the best answer ending at i. The final answer is the maximum over all i, not dp of the last index.

Run the animation above on your own input, or watch the 1:58 video explanation of Longest Increasing Subsequence with a dry run and Java code.

How to solve Longest Increasing Subsequence

Why the obvious approach is slow

The key idea

Remember

More Dynamic Programming problems