Python DP solution O(N^2)


  • 0
    U
    class Solution(object):
        def largestDivisibleSubset(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            cache = [1] * len(nums)
            parent = range(len(nums))
            max_length = 0
            max_index = None
            nums = sorted(nums)
            
            for i in xrange(len(nums)):
                for j in xrange(i):
                   if nums[i] % nums[j] == 0 and cache[j] + 1 > cache[i]:
                       cache[i] = cache[j] + 1
                       parent[i] = j
                
                if cache[i] >= max_length:
                    max_length = cache[i]
                    max_index = i
            
            ans = []
            while parent and parent[max_index] != max_index:
                ans.append(nums[max_index])
                max_index = parent[max_index]
            
            if parent:
                ans.append(nums[max_index])
            
            return ans
                       
            
                    
            
    

Log in to reply
 

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