Python short solution


  • 0
    A
    # class Solution(object):
        def largestDivisibleSubset(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            if len(nums) == 0:
                return nums
            # sort 
            nums = sorted(nums)
            n = len(nums)
            cnt, idx = [0 for _ in range(n)], [-1 for _ in range(n)]
            globalMax, globalBest = 0, 0
            for pos in range(len(nums)-1,-1,-1):
                if pos == len(nums)-1:
                    cnt[pos], idx[pos] = 1, -1
                else:
                    currMax, bestPos = 0, pos
                    for i in range(pos+1, len(nums)):
                        if nums[i] % nums[pos] == 0 and cnt[i] + 1 > currMax:
                            currMax, bestPos = cnt[i] + 1, i
                    cnt[pos], idx[pos] = currMax, -1 if currMax == 0 else bestPos
                    if currMax > globalMax:
                        globalMax, globalBest = currMax, pos
            res = []
            while globalBest != -1:
                res.append(nums[globalBest])
                globalBest = idx[globalBest]
            return res
    

  • 0
    I

    How did you decide to use dynamic programming for this question?


Log in to reply
 

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