Skip to content
Tutorials Center
My learning

Topics

Lesson 153 of 225 ยท Dynamic Programming

Longest Increasing Subsequence

Learn the longest increasing subsequence in Python: the O(n^2) DP, the O(n log n) bisect method, rebuilding the sequence, counting and common variants.

Take the list [10, 9, 2, 5, 3, 7, 101, 18]. A subsequence keeps some elements in their original order, skipping others freely. An increasing subsequence is one whose values go strictly up. For example 2, 5, 7, 101 works. The longest increasing subsequence (LIS) is the longest such pick. Here its length is 4.

LIS is a perfect teaching problem: it has a simple O(n^2) dynamic programming solution, and a clever O(n log n) one built on binary search. It also appears inside many other problems (nesting envelopes, minimum deletions to sort, scheduling), so it is worth knowing both versions.

A subsequence is not a subarray. A subarray must be contiguous (as in Kadane's algorithm); a subsequence may skip elements.

Brute force: try every subsequence

A list of n elements has 2^n subsequences. For each, check whether it is increasing, and keep the longest. That is O(2^n x n), fine for n = 20 and hopeless for n = 100.

Python Brute force over all subsequences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The O(n^2) dynamic programming solution

State. dp[i] = the length of the longest increasing subsequence that ends exactly at index i. The "ends at i" part is the trick: it lets us extend any earlier subsequence whose last value is smaller.

Transition. Look at every earlier index j < i. If nums[j] < nums[i], then we can append nums[i] to the best subsequence ending at j:

TEXT
dp[i] = 1 + max(dp[j])   for all j < i with nums[j] < nums[i]
dp[i] = 1                if no such j exists
answer = max(dp)         (the best end can be anywhere)

The final answer is max(dp), not dp[-1], because the winning subsequence need not end at the last element.

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

TEXT
index:   0   1   2   3   4   5    6    7
nums:   10   9   2   5   3   7  101   18
dp:      1   1   1   2   2   3    4    4
                         |   |    |    |
   5 follows 2 ---------+   |    |    |
   3 follows 2 -------------+    |    |
   7 follows 5 (or 3) ----------+    |
   101 follows 7 -------------------+
   18 follows 7 ---------------------+

There are two nested loops, so the time is O(n^2) and the space is O(n).

Python LIS length with an O(n^2) DP table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Rebuilding the actual subsequence

Length alone is rarely the whole job. Keep a parent[i] array that remembers which j gave the best dp[i], then walk back from the best end.

Python Reconstruct one longest subsequence

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When several longest subsequences exist, which one you get depends on tie-breaking, but the length is always the same.

The O(n log n) method: patience sorting

The O(n^2) solution wastes work. Think about it differently: keep a list tails where tails[k] is the smallest possible last value of an increasing subsequence of length k + 1. Smaller tails are better, because they are easier to extend.

Two facts make this work:

  1. tails is always sorted increasing. (A length-3 subsequence contains a length-2 one that ends in something smaller.)
  2. For each new number x, find the first tail that is >= x and replace it with x. If every tail is smaller than x, append x, because we have found a longer subsequence.

Finding "the first tail >= x" is exactly bisect_left. The answer is the final length of tails.

TEXT
nums = [10, 9, 2, 5, 3, 7, 101, 18]

x=10  tails = [10]
x=9   tails = [9]            (9 replaces 10)
x=2   tails = [2]
x=5   tails = [2, 5]         (append)
x=3   tails = [2, 3]         (3 replaces 5)
x=7   tails = [2, 3, 7]      (append)
x=101 tails = [2, 3, 7, 101] (append)
x=18  tails = [2, 3, 7, 18]  (18 replaces 101)

length of tails = 4 = LIS length

tails is not the LIS itself. After the last step above it holds [2, 3, 7, 18], which happens to be valid, but in general it can mix elements from different subsequences. Only its length is guaranteed correct.

Each element costs one binary search, so the total is O(n log n) time and O(n) space.

Python LIS with bisect (patience sorting)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why bisect_left for strictly increasing

bisect_left finds the first tail that is >= x, so an equal value replaces an equal tail instead of extending it. That gives strictly increasing sequences. If the problem allows equal neighbors (a non-decreasing subsequence), switch to bisect_right.

Python Strict vs non-decreasing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting how many LIS exist

Keep two arrays: length[i] (as before) and count[i] = how many longest subsequences end at i. When a better length is found, reset the count; when an equal length is found, add to it.

Python Count the longest increasing subsequences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Classic variants

Many problems are LIS in disguise.

  • Minimum deletions to make a list sorted: n - LIS (keep the longest increasing part, delete the rest). For non-decreasing, use the bisect_right version.
  • Longest decreasing subsequence: negate the numbers and run LIS, or reverse the comparison.
  • Longest bitonic subsequence (up then down): compute the LIS ending at each index from the left, the longest decreasing starting at each index (LIS on the reversed list), and take the best left[i] + right[i] - 1.
  • Russian doll envelopes: sort envelopes by width ascending and, for equal widths, by height descending, then run strict LIS on the heights. The descending tie-break stops two envelopes of the same width from nesting.
  • Longest chain of pairs and box stacking reduce to sort-then-LIS.
Python LIS variants: deletions and envelopes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which version should I use?

Version Time Space Notes
Brute force O(2^n x n) O(n) Only for tiny n
DP table O(n^2) O(n) Easy to extend: counting, parents, variants
Patience + bisect O(n log n) O(n) Fastest; length only unless you add bookkeeping

For n up to about 5,000 the quadratic DP is fine. For n around 100,000 you need the bisect method. See the complexity cheat sheet for what each limit allows.

Common mistakes

  • Returning dp[-1] instead of max(dp).
  • Using bisect_right for a strict problem (it counts equal values as extending).
  • Treating tails as the answer sequence. It only gives the length.
  • Confusing subsequence with subarray: LIS may skip elements.
  • Forgetting the empty list, where max([]) raises an error.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the O(n^2) DP, what does dp[i] mean?

    Fixing the end element lets any earlier, smaller element extend it. The overall answer is then max(dp), since the best subsequence can end anywhere.
  2. 2. What is the LIS length of [3, 1, 2, 1, 8, 5, 6]?

    For example 1, 2, 5, 6 is increasing and has length 4. No increasing subsequence of length 5 exists.
  3. 3. In the O(n log n) method, what does tails[k] store?

    Keeping the smallest possible tail for each length leaves the most room to extend later. This is why tails stays sorted and can be binary searched.
  4. 4. Which change turns the strict LIS into the longest non-decreasing subsequence?

    bisect_right places an equal value after existing equal tails, so equal values extend the sequence instead of replacing a tail.
  5. 5. What is the minimum number of deletions to make a list strictly increasing?

    Keep the longest increasing subsequence and delete everything else, which removes n minus its length elements.

Summary

  • A subsequence keeps order but may skip elements; LIS is the longest strictly increasing one.
  • DP: dp[i] = 1 + max(dp[j]) over earlier smaller values; the answer is max(dp). O(n^2) time, O(n) space.
  • Patience sorting keeps tails, the smallest tail per length, and uses bisect_left for O(n log n); only its length is the answer.
  • Track a parent array to rebuild a subsequence, and a count array to count them all.
  • Variants (deletions, envelopes, bitonic, decreasing) reduce to LIS after sorting or reversing.

Next: LCS and Edit Distance