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.
给出一个不重复的正整数集合，找出满足 Si % Sj = 0 或者 Sj % Si = 0 的最长可整除子序列。如果有多个解，只需返回任意一个即可
nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)
nums: [1,2,4,8]
Result: [1,2,4,8]
动态规划解。这道题和LIS非常相似，LIS的要求是递增，而最长可正整除序列的要求则是可整除。所以只要我们先将列表排序，这样只需判断 Si % Sj = 0 （i > j），再接下来就和LIS完全一样了（和我上一篇差不多就不写了）。不过这里需要输出一种结果。所以我们还需要额外保存每个元素的上一个元素索引。
class Solution(object): def largestDivisibleSubset(self, nums): """ :type nums: List[int] :rtype: List[int] """ if len(nums) == 0: return [] # 先排序保证只需要相除一次 nums.sort() dp = [1] * len(nums) dp_index = [-1] * len(nums) # 保存元素的上一个元素的索引，用于得到序列 max_len = 1 # 维护一个最长子序列的长度 for index_n, n in enumerate(nums): for i in range(index_n): if n % nums[i] == 0 and dp[i] + 1 > dp[index_n]: dp[index_n] = dp[i] + 1 dp_index[index_n] = i # 每次更新dp时同时保存其上一个元素的索引 max_len = max(dp[i] + 1, max_len) result = [] # 定位到第一个最长子序列的结尾 index = dp.index(max_len) # 根据dp_index反向保存最长子序列 while index != -1: result.append(nums[index]) index = dp_index[index] # 得到上一个元素的索引 result.reverse() # 倒序 return result新闻热点
疑难解答
