Standard Bar Dynamic Programming · DP on LIS O(n^2) · O(n)
A workshop assembles demonstration kits of gears where every pair in a kit must mesh by exact ratio — one gear's tooth count divides the other's. The procurement list holds distinct tooth counts, and the packer wants the largest compatible kit. Sorting the counts turns any chain of divisibility into a rising sequence.
Input: An array nums of distinct positive integers.
Output: Return any largest subset of nums in which every pair satisfies the divisibility rule.
1 <= n <= 10001 <= nums[i] <= 2 * 10^9all values are distinctInput: {"nums":[1,2,3]}
Output: [1,2]
1 divides 2; [1, 3] is an equally valid kit.
Input: {"nums":[1,2,4,8]}
Output: [1,2,4,8]
The whole set forms one divisibility chain 1 | 2 | 4 | 8.