[Swift]LeetCode368. 最大整除子集 | Largest Divisible Subset
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10277728.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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..<number
10 {
11 for j in stride(from:i,through:0,by:-1)
12 {
13 if nums[i] % nums[j] == 0 && dp[i][0] < dp[j][0] + 1
14 {
15 dp[i][0] = dp[j][0] + 1
16 dp[i][1] = j
17 if mx < dp[i][0]
18 {
19 mx = dp[i][0]
20 mx_idx = i
21 }
22 }
23 }
24 }
25 for i in 0..<mx
26 {
27 res.append(nums[mx_idx])
28 mx_idx = dp[mx_idx][1]
29 }
30 return res
31 }
32 }