> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/368-largest-divisible-subset.md).

# 368     Largest Divisible Subset

## 368. [Largest Divisible Subset](https://leetcode.com/problems/largest-divisible-subset/description/)

## 1. Question

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]
```

## 2. Implementation

思路: 因为要找的是最大的subset，我们发现最后我们要找的结果和它**当前的位置是无关的，**&#x6240;以为了方便比较，我们先**对输入的数组排序。**&#x7136;后我们用类似于找**Longest Increasing Subsequence**的方式找到最大的divisible subset。我们用count和preIndex两个数组分别记录以下信息: count\[i]表示在位置i之前的，最大的divisible subset的size，preIndex\[i]记录i之前的上一个divisible subset的元素。比如如果 nums\[i] % nums\[j] == 0 and j < i, preIndex\[i] = j. 最后有一点要注意的是，如果subset只有1个元素，那么很明显这是个合法的解(自己余自己等于0)，所以**第一个for loop里我们先从i = 0开始，而不是i = 1**

**(1) DP**

```java
class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> res = new ArrayList<>();

        if (nums == null || nums.length == 0) {
            return res;
        }

        Arrays.sort(nums);
        int n = nums.length;
        int[] count = new int[n];
        int[] preIndex = new int[n];
        int max = 0, index = -1;


        for (int i = 0; i < n; i++) {
            count[i] = 1;
            preIndex[i] = -1;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] % nums[j] == 0 && (1 + count[j] > count[i])) {
                    count[i] = count[j] + 1;
                    preIndex[i] = j;
                }
            }
             if (count[i] > max) {
                max = count[i];
                index = i;
            }
        }

        while (index != -1) {
            res.add(nums[index]);
            index = preIndex[index];
        }
        return res;
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(n^2), 空间复杂度O(n)