-
Notifications
You must be signed in to change notification settings - Fork 461
Expand file tree
/
Copy path368_Largest_Divisible_Subset.py
More file actions
71 lines (58 loc) · 1.6 KB
/
Copy path368_Largest_Divisible_Subset.py
File metadata and controls
71 lines (58 loc) · 1.6 KB
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
# DP bottom-up tabulation
class Solution(object):
def largestDivisibleSubset(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
# The container that holds all intermediate solutions.
# key: the largest element in a valid subset.
subsets = {-1: set()}
for num in sorted(nums):
currentSubSets = []
for key in subsets:
if num % key == 0:
newSet = set(subsets[key])
newSet.add(num)
currentSubSets.append(newSet)
if currentSubSets is not None:
subsets[num] = max(currentSubSets, key=len)
else:
subsets[num] = {num}
return list(max(subsets.values(), key=len))
# # DP top-down recursive - To Be Finished
# class Solution(object):
# def largestDivisibleSubset(self, nums):
# """
# :type nums: List[int]
# :rtype: List[int]
# """
# # The container that holds all intermediate solutions.
# # key: the largest element in a valid subset.
# if not nums:
# return []
# nums.sort()
# memo = {}
# self.largestDivisibleSubsetHelper(nums, memo)
# return list(max(memo.values(), key=len))
# def largestDivisibleSubsetHelper(self, nums, memo):
# """
# :type nums: List[int]
# :rtype: List[int]
# """
# pass
"""
1,2,3
i
j
1%2=0 or 2%1=0 > 1,2
1%3=0 or 3%1=0 > 1,2
1,2,4,8
12 14 18 24 28 48 >>1248
1248
1 2 4 8
1 1
2 2
4 4
8 8
"""