算法

(数学+DP) $O(n^2)$

对于$subset$，如果现在遇到一个新的元素$n$，那么$n$能否被加入$subset$呢？
只需满足两个条件：

• $n$ % 比$n$小的最大的数 == $0$
• 比$n$大的最小的数% $n$ == $0$

第一个条件就能使得所有比$n$小的元素都是$n$的因数；
第二个条件保证所有比$n$大的元素都是$n$的倍数。

我们可以先对$nums$进行排序，于是$subset$就是有序的了，所以现在只需要考虑第一个条件即可，而比$n$小的最大的数也就是$subset$中的最后的元素，可以以$O(1)$的时间去判断，即$n \ \% \ max \ of \ subset == 0$。

然后我们来定义$dp$的状态：
$dp[i]$：以$nums[i]$为结尾满足题意的$subset$的长度，也就是最大的$subset$的长度
然后它的转移方程就是$dp[i] = 1 + max \{dp[j]\}$，其中$nums[i]\%nums[j]==0$，并且$0\leqslant j < i$。

Java 代码

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        if (n == 0) return new ArrayList();
        Arrays.sort(nums);
        int maxIdx = 0;
        List<Integer>[] res = new ArrayList[n];
        for (int i = 0; i < n; ++i) {
            int max = i;
            int maxLen = 0;
            for (int j = 0; j < i; ++j) {
                if (nums[i] % nums[j] == 0 && maxLen < res[j].size()) {
                    max= j;
                    maxLen = res[j].size();
                }
            }
            res[i] = new ArrayList();
            res[i].addAll(res[max]);
            res[i].add(nums[i]);
            if (res[maxIdx].size() < res[i].size()) maxIdx = i;
        }
        return res[maxIdx];
    }
}