if we sort, we can iterate from j = i-1 to 0 and break once its divisible. has a 10x faster runtime for most.
dp = [1] * len(nums)
nums.sort()
res = 0
for i in range(1, len(nums)):
for j in range(i-1, -1, -1):
if nums[i] % nums[j] == 0:
dp[i] = dp[j] + 1
res = max(res, dp[i])
break
0.04176688194274902 (given solution)
0.003387928009033203 (above solution)
27
it is faster but it is incorrect 
take a set “1 2 3 4 8 16 32 33 1056 (= 32*33)”
a set ending up with 32 has 6 elements and a set ending with 33 has only 3 elements.
Your algorithm would determine that the largest set including number 1056 has size 4 instead of 7.
Here is a method that utilizes breaking early correctly in C#:
nums.Sort();
var maxSubsets = new List<int>();
int largestSubset = 1;
for (int i = 0; i < nums.Count; i++) {
int maxSubset = 0;
for (int j = i - 1; j >= 0; j--) {
if (nums[i] % nums[j] == 0 && maxSubsets[j] > maxSubset) {
maxSubset = maxSubsets[j];
if (maxSubset == largestSubset) {
largestSubset++;
break;
}
}
}
maxSubsets.Add(maxSubset + 1);
}
return largestSubset;
Please rewrite the solution explanation since it is poorly worded. Also please add the Top-Down Solution as well. Here is mine. Using the same mathematical logic as the bottom up solution, sort the list and use the Longest Increasing Subsequence template to solve the Problem. Here is my python solution for it:
from typing import List
def find_largest_subset(nums: List[int]) → int:
def dfs(i, nums, maxCount, visited):
if i == 0:
return 0
if i in visited:
return visited[i]
longest = dfs(0, nums, maxCount, visited) + 1
ni = nums[i - 1]
for j in range(1, i):
nj = nums[j - 1]
currLongest = dfs(j, nums, maxCount, visited)
if ni % nj == 0:
longest = max(longest, currLongest + 1)
maxCount[0] = max(maxCount[0], longest)
visited[i] = longest
return longest
visited = {}
maxCount = [0]
nums.sort()
dfs(len(nums), nums, maxCount, visited)
return maxCount[0]
if name == ‘main’:
nums = [int(x) for x in input().split()]
res = find_largest_subset(nums)
print(res)
Are you sure your code works? It appears that your code returns the longest subset with nums[i - 1] included for the set size i. However, for size i, it might be the case that i - 1 might not be included. For example, 1 2 4 8 9.