largest divisible subset

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        n=len(nums)
        dp=[1]*(n)
        total=1
        for i in range(1,n):
            maxi=0
            for j in range(i):
                if nums[i]%nums[j]==0:
                    maxi=max(maxi,dp[j])
            dp[i]+=maxi
            total=max(total,dp[i])
            
        for i in range(n-1,-1,-1):
            if dp[i]==total:
                ind=i
                break
        out=[nums[ind]]
        last=ind
        for i in range(ind-1,-1,-1):
            if dp[i]+1==total and out[-1]%nums[i]==0:
                out.append(nums[i])
                ind=i
                total=dp[i]
        return out 
        
        
        

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:

answer[i] % answer[j] == 0, or
answer[j] % answer[i] == 0
If there are multiple solutions, return any of them.

 

Example 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.
Example 2:

Input: nums = [1,2,4,8]
Output: [1,2,4,8]