Longest Increasing Subsequence

Eight books stand on a shelf, with heights 5, 2, 8, 6, 3, 6, 9, 7. You want the books that stay to rise from left to right, strictly taller each time, and you are only allowed to take books off, never to reorder them. What is the fewest you can remove?

Turn it around: find the most books you can keep. Those form the longest increasing subsequence (LIS): the longest list of values, in their original order but not necessarily side by side, where each one is bigger than the one before. Here it has length 4, for example 2, 3, 6, 9, so you remove 4 books.

#Pick the state carefully

The 1D DP habit says: let best[i] be the answer for the first i books. Try it. To decide whether book i can join, you need to know the last height of the sequence you are extending, and "the best for the first i books" does not tell you that.

So pin the end down. Make each cell about sequences that end exactly at book i. Then the last height is h[i], and extending is easy to check.

1. State. len[i] is the length of the longest increasing subsequence that ends at index i, using h[i] as its last value.
2. Recurrence. The value before h[i] is some earlier, smaller h[j]. Take the best of those: len[i] = 1 + max(len[j]) over all j < i with h[j] < h[i].
3. Base case. If no earlier value is smaller, len[i] = 1: the book on its own.
4. Order. Each cell reads cells to its left. Fill left to right.
5. Answer. The largest value anywhere in len, because the longest sequence can end at any book.

Unlike the shifts in the 1D lesson, each cell here looks back at every earlier cell, not just two.

for i from 0 to n - 1:  len[i] = 1                     # just h[i] on its own  for j from 0 to i - 1:    if h[j] < h[i]:      len[i] = max(len[i], len[j] + 1)return max(len)

function lisLength(heights) {
  const n = heights.length;
  const len = new Array(n).fill(1); // each value alone has length 1
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (heights[j] < heights[i]) {
        len[i] = Math.max(len[i], len[j] + 1); // extend the run ending at j
      }
    }
  }
  return len.reduce((a, b) => Math.max(a, b), 0); // best over every end
}
 
lisLength([5, 2, 8, 6, 3, 6, 9, 7]); // 4

def lis_length(heights):
    n = len(heights)
    length = [1] * n  # each value alone has length 1
    for i in range(n):
        for j in range(i):
            if heights[j] < heights[i]:
                length[i] = max(length[i], length[j] + 1)  # extend the run ending at j
    return max(length, default=0)  # best over every end
 
lis_length([5, 2, 8, 6, 3, 6, 9, 7])  # 4

#Faster: keep the lowest ending for each length

The table compares every pair, which is about 50 million comparisons for 10,000 values. A different record brings that down to about 14 steps per value, around 140,000 in all. Keep a list called tails, where tails[k] is the smallest last value of any increasing subsequence of length k + 1 seen so far.

Why the smallest? If two sequences have the same length, the one that ends lower is easier to extend: anything that fits after the higher one also fits after the lower one. So for each length, you only need to remember the lowest ending.

For each new value x, find the first tail that is >= x. If there is none, x is bigger than every tail and makes a longer sequence: append it. Otherwise replace that tail with x: a sequence of that length can now end lower. tails stays sorted the whole time, so the search is a binary search.

tails = []for x in heights:  k = first index with tails[k] >= x   # binary search  if k == len(tails): append x  else: tails[k] = xreturn len(tails)

function lisLengthFast(heights) {
  const tails = [];
  for (const x of heights) {
    let lo = 0;
    let hi = tails.length; // find the first tail >= x
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = x; // replaces a tail, or appends when lo === tails.length
  }
  return tails.length;
}
 
lisLengthFast([5, 2, 8, 6, 3, 6, 9, 7]); // 4

from bisect import bisect_left
 
def lis_length_fast(heights):
    tails = []
    for x in heights:
        k = bisect_left(tails, x)  # first tail >= x
        if k == len(tails):
            tails.append(x)  # longer than anything so far
        else:
            tails[k] = x  # same length, lower ending
    return len(tails)
 
lis_length_fast([5, 2, 8, 6, 3, 6, 9, 7])  # 4

#Common mistakes

#Check yourself

#What to practise next

If the tails search felt hard to follow, rework Binary Search with the "first position where the condition holds" version in mind. Then try Typing Class Progress, and write the five steps in words before you write any code.