Largest Divisible Subset

这题主要麻烦在于找出这个结果，因为DP是一种求可行性的算法而不是一种找出制定结果的算法，这里只能使用一个额外项来储备每一个位置为皆为的subset的上一个点是什么，最后用while循环一遍收了，另外此题的数组顺序是无序的，必须排序，时间复杂度是O(n^2)，所以排序不构成影响

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        nums.sort()
        n = len(nums)
        dp = [[1, None] for _ in xrange(n)]

        maxCount, maxIndex = 0, None
        for i in xrange(n):
            for j in xrange(i):
                if nums[i] % nums[j] == 0:
                    if dp[j][0] + 1 > dp[i][0]:
                        dp[i] = [dp[j][0] + 1, j]
            if dp[i][0] > maxCount:
                maxCount = dp[i][0]        
                maxIndex = i

        result = []
        while maxIndex is not None:
            result = [nums[maxIndex]] + result
            maxIndex = dp[maxIndex][1]

        return result