307. Largest Divisible Subset
You receive nums, an array of distinct positive integers. A subset is called divisible if for every pair of values (a, b) it contains, one of them divides the other evenly — either a % b == 0 or b % a == 0.
Return the largest divisible subset of nums, listed in increasing order. Every input is constructed so that the largest divisible subset is unique, so there is exactly one correct answer.
A single element is always a divisible subset by itself.
Example 1:
Input: nums = [1, 2, 4, 8, 3]
Output: [1, 2, 4, 8]
Explanation: In {1, 2, 4, 8} every smaller value divides every larger one. Adding 3 breaks the property (3 and 2 don't divide each other), and no other subset reaches size 4.
Example 2:
Input: nums = [4, 8, 10, 240]
Output: [4, 8, 240]
Explanation: 4 | 8, 8 | 240, and 4 | 240, so {4, 8, 240} is divisible. 10 can't join: 10 doesn't divide 8 and 4 doesn't divide 10.
Constraints:
- 1 ≤ nums.length ≤ 1000
- 1 ≤ nums[i] ≤ 2 * 10⁹
- All values in nums are distinct.
- The largest divisible subset of every input is unique.
Hints:
Sort first. In a sorted divisible subset each element divides the next one, because for distinct values a < b, 'one divides the other' forces a | b — and divisibility chains are transitive. So the problem becomes: find the longest chain where every element divides its successor.
That is Longest Increasing Subsequence with the comparison swapped: instead of nums[j] < nums[i], the link condition is nums[i] % nums[j] == 0. Let dp[i] be the longest chain ending at index i and take the best over all j < i.
dp only gives the size. Store parent[i] — the index j that produced dp[i] — and walk parents backwards from the index with the largest dp to rebuild the subset, then reverse it.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 4, 8, 3]
Expected output: [1, 2, 4, 8]