Medium Problemssubsetoptimizationlinear

Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset in which, for every pair of chosen numbers, the smaller one divides the larger one evenly.

Do this lesson first: house robber

Example input

nums = [1, 2, 3, 4, 8, 9, 12, 16, 24, 36] (sorted ascending)

Expected output

5

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = 1 + max over every j < i with nums[i] % nums[j] == 0 of dp[j], or 1 if no such j exists

Ask what the next-smaller number in the chain that ends at index i must have been. Since the array is sorted ascending, any earlier number that divides nums[i] evenly is a legal link one step down, so dp[i] extends whichever qualifying earlier index already holds the longest such chain. Checking only that nums[i] divides by a single earlier member is enough, because a chain built this way is automatically consistent all the way down: if a divides b and b divides c, then a divides c too, so the transition never has to re-check any link further back than the one directly below it.

dp[0] = 1 is the only declared base: the smallest number is trivially a divisible chain of one all by itself, and because sorting places 1 there for this fixed array, it also ends up divisible by every later number, so it is read constantly (nums[0] = 1 divides everything). That happens to mean every later index always has at least one qualifying predecessor here, dp[0] itself, so this particular input never produces a zero-dependency compute cell beyond index 0; a differently chosen array could still have one, since the shape depends entirely on whether some earlier number divides the current one. Every other cell depends only on smaller indices, so filling left to right guarantees every candidate that does qualify already holds a real value before it is read. Because the answer is whichever cell ends up largest, not necessarily the last one, the table also has to track that argmax as it fills.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 1 is the only declared base: the smallest number is trivially a divisible chain of one all by itself, and because sorting places 1 there for this fixed array, it also ends up divisible by every later number, so it is read constantly (nums[0] = 1 divides everything). That happens to mean every later index always has at least one qualifying predecessor here, dp[0] itself, so this particular input never produces a zero-dependency compute cell beyond index 0; a differently chosen array could still have one, since the shape depends entirely on whether some earlier number divides the current one. Every other cell depends only on smaller indices, so filling left to right guarantees every candidate that does qualify already holds a real value before it is read. Because the answer is whichever cell ends up largest, not necessarily the last one, the table also has to track that argmax as it fills.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

i=9

1

2

3

4

3

4

5

largest-divisible-subset.ts

1function largestDivisibleSubset(nums) {
2 nums.sort((a, b) => a - b);
3 const dp = new Array(nums.length).fill(1);
4 let best = dp[0];
5 for (let i = 1; i < nums.length; i++) {
6 for (let j = 0; j < i; j++) {
7 if (nums[i] % nums[j] === 0) dp[i] = Math.max(dp[i], dp[j] + 1);
8 }
9 best = Math.max(best, dp[i]);
10 }
11 return best;
12}

Base caseComputedBeing readAnswer

The code, the trap, the variations

largest-divisible-subset.ts

1function largestDivisibleSubset(nums) {
2 nums.sort((a, b) => a - b);
3 const dp = new Array(nums.length).fill(1);
4 let best = dp[0];
5 for (let i = 1; i < nums.length; i++) {
6 for (let j = 0; j < i; j++) {
7 if (nums[i] % nums[j] === 0) dp[i] = Math.max(dp[i], dp[j] + 1);
8 }
9 best = Math.max(best, dp[i]);
10 }
11 return best;
12}

Where people go wrong

Forgetting that sorting the array first is what makes a single divisibility check enough. Without sorting, checking only nums[i] % nums[j] == 0 for j < i would miss chains where a smaller-valued divisor happens to sit later in the input order; sorting ascending guarantees every legal chain reads as a run of increasing values from left to right, so the recurrence never needs to look both directions.

Return one such subset itself, not just its size.
Each cell would need to remember which earlier index it extended, so the chain can be walked backward from the best cell once found; the size recurrence, the sort, and the left-to-right order do not change at all.
Ask for the largest subset where every pair sums to a perfect square instead of dividing evenly.
Only the single predicate inside the inner loop changes, from a division check to a square-sum check; the plus-one, the max over qualifying j, and the argmax-over-the-table answer all stay exactly the same.

Edit Distance Weighted Job Schedulling