★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（）

➤GitHub地址：

➤原文地址： 

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:

Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

Input: [1,2,3]Output: [1,2] (of course, [1,3] will also be ok)

Example 2:

Input: [1,2,4,8]Output: [1,2,4,8]

---

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

如果有多个目标子集，返回其中任何一个均可。 

示例 1:

输入: [1,2,3]输出: [1,2] (当然, [1,3] 也正确)

示例 2:

输入: [1,2,4,8]输出: [1,2,4,8]

---

476ms

1 class Solution { 2     func largestDivisibleSubset(_ nums: [Int]) -> [Int] { 3         var nums = nums.sorted(by:<) 4         var res:[Int] = [Int]() 5         let number:Int = nums.count 6         var dp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:2),count:number) 7         var mx:Int = 0 8         var mx_idx:Int = 0 9         for i in 0..