Question 368. Largest Divisible Subset

Link:

https://leetcode.com/problems/largest-divisible-subset/

My Code:

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        SortedNums = sorted(nums)
        if len(nums) == 0:
            return []
        if len(SortedNums ) ==1:
            return SortedNums
        else:
            #Here we design a list dp, dp[j] is the maximum length list end up with nums[j]
            StoreList = [[SortedNums[0]]]
            for i in range(1,len(SortedNums)):
                NewList =[SortedNums[i]]
                length = 1
                for j in range(i):
                    if SortedNums[i]%SortedNums[j] == 0:
                        Temp =  copy.deepcopy(StoreList[j])
                        Temp.append(SortedNums[i])
                        NewList2 = Temp
                        if len(NewList2) > length:
                            NewList = NewList2
                            length  = len(NewList)
                StoreList.append(NewList)
            Length2 = len(StoreList[0])
            ResultList = StoreList[0]
            for k in range(1,len(StoreList)):
                if len(StoreList[k])> Length2:
                    ResultList = StoreList[k]
                    Length2 = len(ResultList)
            return ResultList

Explanation: First, we need to solve the issue how to check the divisibility. The idea is that for any integers a, b , c if a|b, b|c  then a|c. Hence we just need to sort the num list. Then we design a dp list. df[j] is the maximum list end up with j the element in the number list. Then for j+1, we just need to check for any i <j+1, if nums[j+1] is divisible by nums[i] or not. If it is divisible , then we append the number into the maximum list end up with ith element. Then we pick the maximum length of all and take that as the jth element in the list.