1185. Largest Divisible Subset

Given a set of distinct positive integers nums, return the largest subset (as a sorted list) such that every pair (a, b) in it satisfies a % b == 0 or b % a == 0. If several exist, return the one built by the standard sorted DP reconstruction. The input is JSON {nums}.

Input: JSON {nums}.

Output: Array — the largest divisible subset, sorted ascending.

Examples

Input: {"nums":[1,2,4,8]}
Output: [1,2,4,8]
Explanation: Each divides the next.

Input: {"nums":[1,2,3]}
Output: [1,2]
Explanation: A largest chain of length 2.

Input: {"nums":[3]}
Output: [3]
Explanation: Single element.

Constraints

• 1<=n<=1000
• distinct positive integers

Asked by