https://leetcode.com/problems/largest-divisible-subset/

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.

#### java

https://discuss.leetcode.com/topic/49652/classic-dp-solution-similar-to-lis-o-n-2

Classic DP solution similar to LIS, O(n^2)

Use DP to track max Set and pre index.

https://discuss.leetcode.com/topic/49741/easy-understood-java-dp-solution-in-28ms-with-o-n-2-time

Easy understood Java DP solution in 28ms with O(n^2) time

The basic idea is like:

The old version cant pass the test case [1,2,4,8,9,72] and [4,8,10,240], thanks for that @Yanning and @svc
Here comes the revised version:

https://discuss.leetcode.com/topic/49424/java-solution-in-32ms-o-n-2-time-o-n-space

Java Solution in 32ms O(N^2) time, O(N) space

#### cpp

https://discuss.leetcode.com/topic/49456/c-solution-with-explanations

C++ Solution with Explanations

The key concept here is:
Given a set of integers that satisfies the property that each pair of integers inside the set are mutually divisible, for a new integer S, S can be placed into the set as long as it can divide the smallest number of the set or is divisible by the largest number of the set.

For example, let’s say we have a set P = { 4, 8, 16 }, P satisfies the divisible condition. Now consider a new number 2, it can divide the smallest number 4, so it can be placed into the set; similarly, 32 can be divided by 16, the biggest number in P, it can also placed into P.

Next, let’s define:

EDIT: For clarification, the following definitions try to enlarge candidate solutions by appending a larger element at the end of each potential set, while my implementation below is prefixing a smaller element at the front of a set. Conceptually they are equivalent but by adding smaller elements at the front saves the trouble for keeping the correct increasing order for the final answer. Please refer to comments in code for more details.

For an increasingly sorted array of integers a[1 .. n]

T[n] = the length of the largest divisible subset whose largest number is a[n]

T[n+1] = max{ 1 + T[i] if a[n+1] mod a[i] == 0 else 1 }

Now, deducting T[n] becomes straight forward with a DP trick. For the final result we will need to maintain a backtrace array for the answer.

Implementation in C++:

https://discuss.leetcode.com/topic/49456/c-solution-with-explanations/2

T[n] = the length of the largest divisible subset whose largest number is a[n] —- this is not true,

T[n] should be the length of the largest divisible subset whose smallest number is a[n], not largest

#### python

https://discuss.leetcode.com/topic/49455/4-lines-in-python

4 lines in Python

My S[x] is the largest subset with x as the largest element, i.e., the subset of all divisors of x in the input. With S[-1] = emptyset as useful base case. Since divisibility is transitive, a multiple x of some divisor d is also a multiple of all elements in S[d], so it’s not necessary to explicitly test divisibility of x by all elements in S[d]. Testing x % d suffices.

While storing entire subsets isn’t super efficient, it’s also not that bad. To extend a subset, the new element must be divisible by all elements in it, meaning it must be at least twice as large as the largest element in it. So with the 31-bit integers we have here, the largest possible set has size 31 (containing all powers of 2).

https://discuss.leetcode.com/topic/49528/python-dp-n-2-solution

Python dp n^2 solution

We first do some math work. For two numbers, A and B, if A < B, A % B must > 0 (A != 0). The only chance A % B == 0 must be A >= B.

With this idea, we sort the list. Then, the question turns similar to no.300 longest increasing subsequence. For ith number, its largest divisible subset is the max of subset of any j from 0 - i-1 in which nums[i] % nums[j] == 0.