卖萌的弱渣

I am stupid, I am hungry.

Largest Divisible Subsets

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

nums: [1,2,4,8]

Result: [1,2,4,8]

Solution

dp[x] = max(dp[x], dp[y] + 1) 其中： 0 <= y < x 且 nums[x] % nums[y] == 0

(Largest-Divisible-Subset.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # s[d] = set() # 最大数为ｄ的子集
        s = {1:set()}
        for x in sorted(nums):
            s[x] = max((s[d] for d in S if x%d == 0), key=len) | {x}
        return list(max(s.values(),key=len))


# DP
class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []
        ret = []
        nums = sorted(nums)
        n = len(nums)
        # 最大值为nums[i]且满足条件的set，能有多少数dp[i]
        dp = [1]*n
        # 在一个解中，数x之前的数为prev[x]
        prev = [None]*n

        for x in range(n):
            for y in range(x):
                if nums[x] % nums[y] == 0 and dp[y]+1 > dp[x]:
                    dp[x] = dp[y]+1
                    prev[x] = y

        # nums[idx]有最大subset
        idx = dp.index(max(dp))
        ret = []

        while idx != None:
            ret.append(nums[idx])
            idx = prev[idx]
        return ret