Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Dynamic programming

Subsequence DP: the best chain ending here

Lesson · 9 min read · Dynamic programming · Pattern: subsequence DP

For chains that may skip elements, end(i) looks back at every earlier element that may come before i. The LIS recurrence, with the compatibility rule swapped.

The pattern

The longest increasing subsequence generalises: any problem asking for the best chain of elements, kept in order but allowed to skip, where consecutive elements must be compatible in some way. Divides, alternates in sign, increases then decreases.

Subsequence DP

end(i)

  1. = best over earlier j with compatible(j, i) of end(j) ⊕ i, or i on its own.

answer

  1. the best end(i); often a second table (or a second pass from the right) is needed for chains with two phases.

Sorting first is often what makes compatibility transitive: for "every pair divides one another", after sorting it is enough that each element divides the next one in the chain.

Worked example: the largest chain where each divides the next

After sorting [1, 2, 4, 3, 8, 6, 24].

  1. Step 1 / 7
    sorted
    102132436485246
    end
    10·1·2·3·4·5·6

    1 is divisible by nothing earlier: end = 1.

  2. Step 2 / 7
    sorted
    102132436485246
    end
    1021·2·3·4·5·6

    2 is divisible by 1: end = 2.

  3. Step 3 / 7
    sorted
    102132436485246
    end
    102122·3·4·5·6

    3 is divisible by 1: end = 2.

  4. Step 4 / 7
    sorted
    102132436485246
    end
    10212233·4·5·6

    4 is divisible by 1, 2: end = 3.

  5. Step 5 / 7
    sorted
    102132436485246
    end
    1021223334·5·6

    6 is divisible by 1, 2, 3: end = 3.

  6. Step 6 / 7
    sorted
    102132436485246
    end
    102122333445·6

    8 is divisible by 1, 2, 4: end = 4.

  7. Step 7 / 7
    sorted
    102132436485246
    end
    10212233344556

    24 is divisible by 1, 2, 3, 4, 6, 8: end = 5. The longest chain has 5 elements: 1, 2, 4, 8, 24.

How to recognise it

  • "Subsequence", "subset in order", "chain", with a pairwise rule between neighbours.
  • n up to a few thousand: O(n²) is expected.
TimeO(n²)
SpaceO(n)

The problems in this module: