Python DP solution with explanation


  • 1
    M

    The thought process is as following:

    --> the goal is to find largest set of number in which every pair (Si, Sj) of elements satisfies Si % Sj = 0 or Sj % Si = 0
    --> if x can divide by y, then all dividers of x can divide y
    --> if [a,b,x] is the set of number that satisfy the requirement, x is the largest and x can divide y, then [a,b,x,y] also satisfy the requirement

    Python code:

    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        l = len(nums)
        if l <= 1:
            return nums
        nums = sorted(nums)
        mem = [[x] for x in nums]
        index = 0
        
        for i in range(1,l):
            maxi = i
            for j in range(i):
                if nums[i]%nums[j] == 0 and len(mem[j]) + 1 > len(mem[maxi]):
                    maxi = j
            if maxi != i:
                mem[i] = mem[maxi]+mem[i]
                
            if len(mem[i]) > len(mem[index]):
                index = i
    
        return mem[index]

Log in to reply
 

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