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新聞熱點
疑難解答
