## Algorithm

Problem Name: 368. Largest Divisible Subset

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 * 109`
• All the integers in `nums` are unique.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const largestDivisibleSubset = function(nums) {
const n = nums.length;
if(n === 0 || n === 1) return nums
let maxSize = 0;
const dp = Array(n).fill(1)
nums.sort((a, b) => a - b)
for(let i = 1; i < n; i++> {
for(let j = i - 1; j >= 0; j--) {
if(nums[i] % nums[j] === 0) {
const tmp = dp[j] + 1
if(tmp > dp[i]) dp[i] = tmp
}
}
if(dp[i] > maxSize) maxSize = dp[i]
}
const res = []
let pivot = 0
for(let i = n - 1; i >= 0; i--) {
if(dp[i] === maxSize && (pivot % nums[i] === 0)) {
pivot = nums[i]
maxSize--
res.push(nums[i])
}
}

return res
};
``````
Copy The Code &

Input

cmd
nums = [1,2,3]

Output

cmd
[1,2]

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def largestDivisibleSubset(self, nums):
dp, n = [[num] for num in sorted(nums)], len(nums)
for i in range(n - 1):
for j in range(i + 1, n):
if not dp[j][-1] % dp[i][-1] and len(dp[i]) >= len(dp[j]):
dp[j] = dp[i] + dp[j][-1:]
return dp and sorted(dp, key = len)[-1]
``````
Copy The Code &

Input

cmd
nums = [1,2,3]

Output

cmd
[1,2]

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _0368_LargestDivisibleSubset
{
public IList < int> LargestDivisibleSubset(int[] nums)
{
var n = nums.Length;
if (n <= 0) return nums;

Array.Sort(nums);
var length = new int[n];
var prevIndex = new int[n];

for (int i = 0; i  <  n; i++)
{
length[i] = 1;
prevIndex[i] = -1;

for (int j = 0; j  <  i; j++)
{
if (nums[i] % nums[j] == 0)
{
if (length[j] + 1 > length[i])
{
length[i] = length[j] + 1;
prevIndex[i] = j;
}
}
}
}

var maxDistance = 0;
var index = -1;
for (int i = 0; i  <  n; i++)
{
if (length[i] > maxDistance)
{
maxDistance = length[i];
index = i;
}
}

var result = new List < int>();
while (index != -1)
{
index = prevIndex[index];
}

return result;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [1,2,4,8]

Output

cmd
[1,2,4,8]