LeetCode 368 Largest Divisible Subset - Walkthrough

Find the largest subset where every pair $(a, b)$ has $a | b$ or $b | a$. Sort and apply LIS-like DP. Sort the array.

For each element, extend from any previous element that divides it. Example: $[1, 2, 4, 8, 3]$ → sorted: $[1, 2, 3, 4, 8]$. DP: $[1, 2, 2, 3, 4]$. Subset: $\{1, 2, 4, 8\}$. observation: if the array is sorted and $a | b$, then any element $c$ in the chain with $c | a$ also divides $b$. Transitivity holds.