Largest Divisible Subset LeetCode solution in Python

1
class Solution:
2
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
3
        nums.sort()
4
        n = len(nums)
5
        dp = [1 for i in range(n)]
6
        hashh = [i for i in range(n)]
7
        ans_ind = 0
8

9
        for i in range(1, n):
10
            for j in range(0, i):
11
                if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
12
                    dp[i] = dp[j] + 1
13
                    hashh[i] = j
14

15
                    # print(dp)
16
                    # print(hashh)
17
        out = []
18
        maxi = dp[0]
19

20
        for i in range(len(nums)):
21
            if dp[i] > maxi:
22
                ans_ind = i
23
                maxi = dp[i]
24

25
        while hashh[ans_ind] != ans_ind:
26
            out.append(nums[ans_ind])
27
            ans_ind = hashh[ans_ind]
28
        out.append(nums[ans_ind])
29
        return out