368. Largest Divisible Subset
1038 ワード
class Solution:
def largestDivisibleSubset(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if not nums:
return []
if len(nums) == 1:
return nums
#
# nums[i] j < i nums[i] % nums[j] == 0
nums.sort()
dp = [1] * len(nums) # dp[i] nums[i]
pre = [0] * len(nums) # pre[ i] = 1 j
maxSize = maxi = 0
for i in range(len(nums)):
for j in range(i):
if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
pre[i] = j
if dp[i] > maxSize:
maxSize = dp[i]
maxi = i
res = []
i = maxi
#
for _ in range(maxSize):
res.append(nums[i])
i = pre[i]
return res[::-1]