题目描述
Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:
- answer[i] % answer[j] == 0, or
- answer[j] % answer[i] == 0 If there are multiple solutions, return any of them.
Example 1:
Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.
Example 2:
Input: nums = [1,2,4,8]
Output: [1,2,4,8]
Constraints:
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 2 * 10^9
- All the integers in nums are unique.
题目分析
根据题意，我们要求的是可互相整除的最大子集；假设集合A中所有元素可互相整除，不妨设 a1 < a2 < a3 < ... < an; 假设有ax > an，且ax%an == 0，则必然有A中所有元素可整除ax
依据上述推理，我们可以利用dp方式求解，假设nums是升序的，dp[i]表示以nums[i]结尾的符合条件的最大子集
如果nums[j] % nums[i] == 0, 则dp[j] = max(dp[i]+1, dp[j])
综上，代码如下:
示例代码
// dp
func largestDivisibleSubset(nums []int) []int {
// ans[i] 表示到nums[i]结尾的最大 divisible subset的元素个数
ans := make([]int, len(nums))
// base case
if len(nums) <= 1 {
return nums
}
// 排序, 便于后续比较
sort.Slice(nums, func(a int, b int) bool {
return nums[a] < nums[b]
})
maxlen := 1
// 最大可互相整除子集的最后一个元素下标
end := 0
// path用来记录最大可互相整除子集的生成“路径”, 类似链表
path := make([]int, len(nums))
// 初始化: 以nums[i]为结尾的最大可互相整除子集数量至少有其本身，故初始化为1
for i := 0; i < len(nums); i++ {
ans[i] = 1
}
for i := 1; i < len(nums); i++ {
for j := i - 1; j >= 0; j-- {
// nums[i] 可被 nums[j] 整除，则说明nums[i]也可被ans[j]中的所有元素整除
// 则将ans[i]更新为ans[j] + 1 , 即原先子集元素加上nums[i]
if nums[i]%nums[j] == 0 && ans[j]+1 > ans[i] {
ans[i] = ans[j] + 1
// path[i]指向j
path[i] = j
}
}
// 更新最大值
if ans[i] >= maxlen {
maxlen = ans[i]
end = i
}
}
res := []int{}
// 通过path将最大可互相整除子集的元素找出来
for i := 0; i < maxlen; i++ {
res = append(res, nums[end])
end = path[end]
}
return res
}