368 - Largest Divisible Subset
Written on September 12, 2017
Tweet
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.
class Solution(object):
def largestDivisibleSubset(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if not nums:
return []
nums.sort()
dp = [1] * len(nums)
index = [-1] * len(nums)
max_count, start = 0, -1
for i in xrange(len(nums)):
for j in reversed(xrange(i)):
if nums[i] % nums[j] == 0:
if dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
index[i] = j
if dp[i] > max_count:
max_count = dp[i]
start = i
ret = []
while start != -1:
ret.append(nums[start])
start = index[start]
return ret