Dynamic Programming • LIS Pattern

Largest Divisible Subset

Find the largest subset where every pair (a, b) satisfies a % b == 0 or b % a == 0. Uses the LIS pattern with trace-back.

Try Interactive Simulator

Overview

This is a direct application of the Longest Increasing Subsequence (LIS) pattern. By sorting the array first, we guarantee `a < b`, so we only need to check if `b % a == 0`.

The DP Array

`dp[i]` stores the length of the longest divisible subset ending at index `i`. It behaves exactly like LIS.

The Hash Array

To reconstruct the actual subset (not just the length), we use a `hash` array. `hash[i]` stores the index of the previous element in the optimal subset.

Trace Back

We find the index with the maximum `dp` value, and trace backwards using `hash[i]` until `hash[i] == i`.

1

i=0

2

i=1

4

i=2

8

i=3

Length (dp)

1

Parent (hash)

0

1

2

3

Code Tracker

:::

1nums.sort((a, b) => a - b);

2let dp = Array(n).fill(1);

3let hash = Array(n).fill(0).map((_, i) => i);

4for (let i = 1; i < n; i++) {

5 for (let j = 0; j < i; j++) {

6 if (nums[i] % nums[j] === 0 && dp[j] + 1 > dp[i]) {

7 dp[i] = dp[j] + 1;

8 hash[i] = j;

9 }

10 }

11}