leetcode - 368. Largest Divisible Subset

Description

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]

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 2 * 10^9
All the integers in nums are unique.

Solution

Solved after help…

Use dp[i] to keep track of the length of longest subset that ends with nums[i], then the transformation equation is:
$$dp[i]=1+\max (dp[j]),\forall nums[i]\%nums[j]==0$$

Because we need to return the longest subset, so when updating the dp, we add another dimension to remember j that we finally choose.

Time complexity: $o(n^2)$
Space complexity: $o(n)$

Code

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        dp = [[1, i] for i in range(len(nums))]
        nums.sort()
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    if dp[j][0] + 1 > dp[i][0]:
                        dp[i][0] = dp[j][0] + 1
                        dp[i][1] = j
        max_len = 1
        res = [nums[dp[0][1]]]
        for i in range(len(dp)):
            if dp[i][0] > max_len:
                res = []
                max_len = dp[i][0]
                index = dp[i][1]
                start_i = i
                while index != start_i:
                    res.append(nums[start_i])
                    start_i = index
                    index = dp[start_i][1]
                res.append(nums[start_i])
        return res