Do I need to install Python to try the Longest Increasing Subsequence — O(n²) DP and the patience trick lesson?

No install required. PyRun runs real CPython in your browser via Pyodide (Python compiled to WebAssembly). Works on Chrome, Firefox, Safari, and Edge — desktop or mobile.

← All lessons

Advanced·14 min·dsa · dp · interview

Longest Increasing Subsequence — O(n²) DP and the patience trick

Longest Increasing Subsequence — two solutions

Given [10, 9, 2, 5, 3, 7, 101, 18], find the longest strictly increasing subsequence. Answer: 4 (e.g. [2, 3, 7, 101]).

The O(n²) DP

Let dp[i] = length of LIS ending exactly at index i. Every element is a subsequence of length 1. For each i, look back at every j < i: if nums[j] < nums[i], extend giving dp[j] + 1.

Final answer = max(dp) — the best ending position wins.

Reach for this first. Honest, easy to reason about, easy to modify (strict vs non-strict, longest decreasing).

The O(n log n) patience-sorting variant

Deal numbers like cards onto piles, each strictly decreasing bottom-to-top. Place each card on the leftmost pile whose top is >= it, or start a new pile. Number of piles = LIS length.

tails[k] = smallest possible tail value of any increasing subsequence of length k+1. For each new x, binary-search where it fits; if largest, append; else overwrite tails[pos].

Key insight: tails itself is not a valid LIS. Its length is the LIS length.

Common pitfalls

Strict vs non-strict. bisect_left gives strictly increasing; bisect_right gives non-decreasing.
Reconstructing the subsequence with O(n log n) needs a parent-pointer array. Fiddly. Use O(n²) if you need the actual subsequence.
Subsequence ≠ substring. Subsequences skip freely.

Try it

Modify lis_n2 to also return one actual longest subsequence. Track parent[i] and walk back from argmax(dp).
Solve Russian Doll Envelopes: sort by w asc, h desc on ties, then LIS on h values.

Practice

3 graded exercises

Write the code, click Check. We’ll tell you exactly what to fix.

Progress0 / 3

Exercise 1
Write lis_length(nums) that returns the length of the longest strictly increasing subsequence in the list. The subsequence does not need to be contiguous.
Exercise 2
Write count_lis(nums) that returns how many distinct longest strictly increasing subsequences exist in the list.
Exercise 3
Write longest_bitonic(nums) that returns the length of the longest subsequence which first strictly increases then strictly decreases. A pure increasing or pure decreasing sequence also counts.

← PreviousCoin Change — unbounded knapsack, minimum coins Next →Edit Distance — 2D DP on a grid

Longest Increasing Subsequence — O(n²) DP and the patience trick

Longest Increasing Subsequence — two solutions

Given [10, 9, 2, 5, 3, 7, 101, 18], find the longest strictly increasing subsequence. Answer: 4 (e.g. [2, 3, 7, 101]).

The O(n²) DP

Let dp[i] = length of LIS ending exactly at index i. Every element is a subsequence of length 1. For each i, look back at every j < i: if nums[j] < nums[i], extend giving dp[j] + 1.

Final answer = max(dp) — the best ending position wins.

Reach for this first. Honest, easy to reason about, easy to modify (strict vs non-strict, longest decreasing).

The O(n log n) patience-sorting variant

Deal numbers like cards onto piles, each strictly decreasing bottom-to-top. Place each card on the leftmost pile whose top is >= it, or start a new pile. Number of piles = LIS length.

tails[k] = smallest possible tail value of any increasing subsequence of length k+1. For each new x, binary-search where it fits; if largest, append; else overwrite tails[pos].

Key insight: tails itself is not a valid LIS. Its length is the LIS length.

Common pitfalls

Strict vs non-strict. bisect_left gives strictly increasing; bisect_right gives non-decreasing.
Reconstructing the subsequence with O(n log n) needs a parent-pointer array. Fiddly. Use O(n²) if you need the actual subsequence.
Subsequence ≠ substring. Subsequences skip freely.

Try it

Modify lis_n2 to also return one actual longest subsequence. Track parent[i] and walk back from argmax(dp).
Solve Russian Doll Envelopes: sort by w asc, h desc on ties, then LIS on h values.

Practice

3 graded exercises

Write the code, click Check. We’ll tell you exactly what to fix.

Progress0 / 3

Exercise 1
Write lis_length(nums) that returns the length of the longest strictly increasing subsequence in the list. The subsequence does not need to be contiguous.
Exercise 2
Write count_lis(nums) that returns how many distinct longest strictly increasing subsequences exist in the list.
Exercise 3
Write longest_bitonic(nums) that returns the length of the longest subsequence which first strictly increases then strictly decreases. A pure increasing or pure decreasing sequence also counts.