Share my easy original DP O(n^2) Python


  • 1
    W
    class Solution(object):
        def largestDivisibleSubset(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            nums.sort()
            n=len(nums)
            if n==0:
                return []
            elif n==1:
                return nums
            leng=[1 for i in range(n)]
            a=[[] for i in range(n)]
            max_l=1
            a[0]=[nums[0]]
            for i in range(1,n):
                for j in range(i-1,-1,-1):
                    if nums[i]%nums[j]==0:
                        if leng[j]+1>leng[i]:
                            leng[i]=leng[j]+1
                            a[i]=a[j]+[nums[i]]
                max_l=max(max_l,leng[i])       
                if leng[i]==1:
                    a[i]=[nums[i]]
            for j in range(n):
                if leng[j]==max_l:
                    return a[j]

  • 0
    G

    Thank you, your solution is very intuitive and clean.


Log in to reply
 

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