My python solution


  • 0
    S
    class Solution(object):
        def largestDivisibleSubset(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            n = len(nums)
            if n == 0:
                return []
            nums.sort()
            dp    = [[]]*n
            dp[0] = [nums[0]]
            maxdp = dp[0]
            
            for i in range(1,n):
                dp[i] = [nums[i]]
                for j in range(i):
                    if nums[i]%dp[j][-1] == 0 and len(dp[i]) < len(dp[j]) + 1:
                        dp[i] = dp[j] + [ nums[i] ]
                if len(maxdp) < len(dp[i]):
                    maxdp = dp[i]
    
            return maxdp
    

Log in to reply
 

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