Largest Divisible Subset – Python 3 (Week 17 – 10)

class Solution:
    """
    @param: nums: a set of distinct positive integers
    @return: the largest subset 
    """
    def largestDivisibleSubset(self, nums):
        # write your code here
        n = len(nums)
        dp = [1] * n
        father = [-1] * n
        
        nums.sort()
        m, index = 0, -1
 
        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    if dp[j] + 1 > dp [i]:
                        dp[i] = dp[j] + 1
                        father[i] = j
                        
            if dp[i] >= m:
                m = dp[i]
                index = i
        
        result = []
        
        for i in range(m):
            result.append(nums[index])
            index = father[index]
            
        return result