Largest Divisible Subset

Problem: Largest Divisible Subset

First, if A is a divisor of B, B is a divisor of C, then A is a divisor of C. So if we sort the list first, when we are finding the largest divisible subset with maximum number as C, a largest divisible subset with maximum number as B is a candidate with C appended. In this way, we can easily find largest divisible subsets with maximum numbers as all possible elements and choose the largest one from them.

Code in Python:

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        nums.sort()
        lengths = [0] * len(nums)
        res = [[] for _ in xrange(len(nums))]
        max_set = []
        max_len = 0
        for i in xrange(len(nums)):
            length, index = 1, i
            for j in xrange(i):
                if nums[i] % nums[j] == 0 and lengths[j] >= length:
                    length, index = lengths[j] + 1, j
            lengths[i], res[i] = length, res[index] + [nums[i]]
            if length > max_len:
                max_len, max_set = length, res[i]
        return max_set