LeetCode 368 Largest Divisible Subset - The LIS Connection

Here's the observation: if you sort the array, then for any chain $a_1, a_2, ..., a_k$ where each divides the next, you only need to check adjacent pairs. Why? If $a$ divides $b$ and $b$ divides $c$, then $a$ divides $c$. Divisibility is transitive.

So after sorting, this becomes LIS where the condition is "divides" instead of "less than". $dp[i]$ = length of longest divisible chain ending at index $i$. The formula: $dp[i] = \max(dp[j] + 1)$ for all $j < i$ where $nums[i] \mod nums[j] = 0$.