Python DP Solution


  • 0
    class Solution(object):
        def largestDivisibleSubset(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            if not nums:
                return []
            nums.sort()
            f = [1] * len(nums)
            for i in range(len(nums)):
                for j in range(i+1,len(nums)):
                    if nums[j] % nums[i] == 0:
                        f[j] = max(f[j], f[i] + 1)
            ans = []
            n = nums[f.index(max(f))]
            for i in range(len(nums)):
                if n % nums[i] == 0 and (not ans or f[i] > f[ans[-1]]):
                    ans.append(i)
            return [nums[i] for i in ans]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.