描述
给一个由 无重复的正整数 组成的集合，找出满足任意两个元素 (Si, Sj) 都有 Si % Sj = 0 或 Sj % Si = 0 成立的最大子集
如果有多种解集，返回其中任意一个。
样例
给一个数组 [1,2,3]，返回 [1,2] 或 [1,3]
给一个数组 [1,2,4,8]，返回 [1,2,4,8]
代码
class Solution:
"""
@param: nums: a set of distinct positive integers
@return: the largest subset
"""
def largestDivisibleSubset(self, nums):
# write your code here
nums.sort()
n = len(nums)
dp = [1 for i in range(n)]
dp_index = [-1 for i in range(n)]
for i in range(1, n):
max_sum = 0
for j in range(0, i):
if nums[i]%nums[j] == 0 and dp[j] > max_sum:
max_sum = dp[j]
dp_index[i] = j
dp[i] += max_sum
sta = 0
maxL = 0
for key, val in enumerate(dp):
if val > maxL:
maxL = val
sta = key
result = []
while sta>=0:
result.append(nums[sta])
sta = dp_index[sta]
return result
思路
思路比较简易，就是最长上升子序列，只不过之前的大小比较条件变化为了整除。但是值得注意的是，它要返回的不是最大整除序列的长度，而是序列数组，所以需要记录。两种思路，一种是用二维数据dp[i][j]直接把数组记录下来，dp[i]里存最大的那个数组，感觉比较麻烦，第二种就比较简单，因为序列之间是有连接关系的，所有用dp_index[i]数组来存下标，dp_index[i]就代表当前数之前的最大整除数序列的最后一个数的下标，这样最后在dp[i]中最大的那个数的下标就是遍历dp_index[i]下标的起始位置。最后把遍历的下标对应的数返回就好。
题目来源
https://www.lintcode.com/problem/largest-divisible-subset/description
