Longest increasing subsequence

Lesson · 12 min read · Dynamic programming · Longest increasing subsequence

The longest run of numbers, not necessarily adjacent, that keeps increasing. The state is "the best subsequence that ends here".

The problem

A subsequence keeps some elements of a list in their original order, skipping any others. In [3, 1, 4, 1, 5, 9, 2, 6] the subsequence 1, 4, 5, 9 is strictly increasing, and no increasing subsequence is longer, so the answer is 4. Trying every subsequence means 2ⁿ of them.

The state: the best that ends here

An increasing subsequence ends at some position i, and the element before it is some earlier, smaller element. That suggests the state end(i): the length of the longest increasing subsequence that ends exactly at position i. Fixing the end is what makes the recurrence possible: to extend a subsequence by nums[i] we only need to know its last element.

Recurrence

end(i)

1 (nums[i] on its own), or
1 + end(j) for any earlier j with nums[j] < nums[i]; take the largest.

answer

the largest end(i) over all i: the best subsequence can end anywhere.

end(5) (the 9) calls end(j) for every smaller earlier element; end(1) and end(0) are reached again and again (red).

Top-down

from functools import lru_cache

def lis(nums):
    @lru_cache(maxsize=None)
    def end(i):                       # longest increasing subsequence ending at i
        best = 1
        for j in range(i):
            if nums[j] < nums[i]:
                best = max(best, 1 + end(j))
        return best
    return max(end(i) for i in range(len(nums))) if nums else 0

int lis(const std::vector<int>& nums) {
    int n = nums.size(), ans = 0;
    std::vector<int> memo(n, 0);
    std::function<int(int)> end = [&](int i) {         // longest increasing subsequence ending at i
        if (memo[i]) return memo[i];
        int best = 1;
        for (int j = 0; j < i; ++j)
            if (nums[j] < nums[i]) best = std::max(best, 1 + end(j));
        return memo[i] = best;
    };
    for (int i = 0; i < n; ++i) ans = std::max(ans, end(i));
    return ans;
}

static int lis(int[] nums) {
    int[] memo = new int[nums.length];
    int ans = 0;
    for (int i = 0; i < nums.length; i++) ans = Math.max(ans, end(nums, i, memo));
    return ans;
}

static int end(int[] nums, int i, int[] memo) {     // longest increasing subsequence ending at i
    if (memo[i] != 0) return memo[i];
    int best = 1;
    for (int j = 0; j < i; j++)
        if (nums[j] < nums[i]) best = Math.max(best, 1 + end(nums, j, memo));
    return memo[i] = best;
}

function lis(nums) {
    const memo = new Array(nums.length).fill(0);
    const end = i => {                                // longest increasing subsequence ending at i
        if (memo[i]) return memo[i];
        let best = 1;
        for (let j = 0; j < i; j++)
            if (nums[j] < nums[i]) best = Math.max(best, 1 + end(j));
        return (memo[i] = best);
    };
    let ans = 0;
    for (let i = 0; i < nums.length; i++) ans = Math.max(ans, end(i));
    return ans;
}

fn lis(nums: &[i64]) -> usize {
    // longest increasing subsequence ending at i
    fn end(i: usize, nums: &[i64], memo: &mut Vec<usize>) -> usize {
        if memo[i] > 0 { return memo[i]; }
        let mut best = 1;
        for j in 0..i {
            if nums[j] < nums[i] { best = best.max(1 + end(j, nums, memo)); }
        }
        memo[i] = best;
        best
    }
    let mut memo = vec![0; nums.len()];
    (0..nums.len()).map(|i| end(i, nums, &mut memo)).max().unwrap_or(0)
}

lis :: [Int] -> Int
lis [] = 0
lis nums = maximum (elems ends)
  where
    n = length nums
    a = listArray (0, n - 1) nums
    -- ends ! i: longest increasing subsequence ending at i, held in a lazy memo table
    ends = listArray (0, n - 1)
      [1 + maximum (0 : [ends ! j | j <- [0 .. i - 1], a ! j < a ! i]) | i <- [0 .. n - 1]] :: Array Int Int

Bottom-up

end(i) reads only smaller indices, so fill left to right.

end(i) for [3, 1, 4, 1, 5, 9, 2, 6].

Step 1 / 8

nums
3011421354952667
end
10·1·2·3·4·5·6·7
Nothing before 3 is smaller: end(0) = 1.
Step 2 / 8

nums
3011421354952667
end
1011·2·3·4·5·6·7
Nothing before 1 is smaller: end(1) = 1.
Step 3 / 8

nums
3011421354952667
end
101122·3·4·5·6·7
4 can follow 3, 1; the longest of those ends at length 1, so end(2) = 2.
Step 4 / 8

nums
3011421354952667
end
10112213·4·5·6·7
Nothing before 1 is smaller: end(3) = 1.
Step 5 / 8

nums
3011421354952667
end
1011221334·5·6·7
5 can follow 3, 1, 4, 1; the longest of those ends at length 2, so end(4) = 3.
Step 6 / 8

nums
3011421354952667
end
101122133445·6·7
9 can follow 3, 1, 4, 1, 5; the longest of those ends at length 3, so end(5) = 4.
Step 7 / 8

nums
3011421354952667
end
10112213344526·7
2 can follow 1, 1; the longest of those ends at length 1, so end(6) = 2.
Step 8 / 8

nums
3011421354952667
end
1011221334452647
6 can follow 3, 1, 4, 1, 5, 2; the longest of those ends at length 3, so end(7) = 4. The answer is the largest entry, 4.

Implementation

The O(n²) table in six languages:

def lis_length(nums):
    end = [1] * len(nums)                 # end[i]: longest increasing run ending at i
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                end[i] = max(end[i], end[j] + 1)
    return max(end)

#include <algorithm>
#include <vector>

int solve(const std::vector<int>& nums) {
    std::vector<int> end(nums.size(), 1);          // longest ending at i
    for (size_t i = 0; i < nums.size(); ++i)
        for (size_t j = 0; j < i; ++j)
            if (nums[j] < nums[i]) end[i] = std::max(end[i], end[j] + 1);
    return *std::max_element(end.begin(), end.end());
}

class Solution {
    public int lisLength(int[] nums) {
        int[] end = new int[nums.length];           // longest ending at i
        int best = 0;
        for (int i = 0; i < nums.length; i++) {
            end[i] = 1;
            for (int j = 0; j < i; j++)
                if (nums[j] < nums[i]) end[i] = Math.max(end[i], end[j] + 1);
            best = Math.max(best, end[i]);
        }
        return best;
    }
}

function lisLength(nums) {
  const end = new Array(nums.length).fill(1);   // longest ending at i
  for (let i = 0; i < nums.length; i++)
    for (let j = 0; j < i; j++)
      if (nums[j] < nums[i]) end[i] = Math.max(end[i], end[j] + 1);
  return Math.max(...end);
}

fn solve(nums: &[i64]) -> i64 {
    let mut end = vec![1i64; nums.len()];          // longest ending at i
    for i in 0..nums.len() {
        for j in 0..i {
            if nums[j] < nums[i] {
                end[i] = end[i].max(end[j] + 1);
            }
        }
    }
    *end.iter().max().unwrap()
}

import Data.Array

solve :: [Int] -> Int
solve nums = maximum (elems end)
  where
    n = length nums
    a = listArray (0, n - 1) nums
    -- end ! i: longest increasing subsequence ending at i (a lazy array fills itself)
    end = listArray (0, n - 1) [1 + maximum (0 : [end ! j | j <- [0 .. i - 1], a ! j < a ! i]) | i <- [0 .. n - 1]] :: Array Int Int

The same code is the reference solution to Longest increasing subsequence, where it is compiled and run against the tests in all six languages.

TimeO(n²)

SpaceO(n)

There is an O(n log n) method: keep, for each length, the smallest possible tail of an increasing subsequence of that length, and binary-search where each new number goes. It is the next problem in this module.