题目描述

给定一组不同的正整数nums，返回最大的子集答案，使得该子集中的每对(answer[i], answer[j])元素满足：

• answer[i] % answer[j] == 0，或者
• answer[j] % answer[i] == 0

如果有多个答案，则返回其中任意一个。

例1：

输入: nums = [1,2,3]
输出: [1,2]
// 这里输出[1,3]亦可

例2：

输入: nums = [1,2,4,8]
输出: [1,2,4,8]

约束条件：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2 * 10⁹
• nums 里的所有整数都是唯一的。

暴力解

暴力解的思路是，遍历出所有的可以互相整除的数组，然后取长度最大的一组返回。

首先为了减少计算量，需要把nums由小到大排序，记做questionArray。 这样顺次从questionArray取出数字比较时，每次取出的数字都比已排序的数字大。 知道数字大小后，判断是否整除就只需要做一次取余运算，可以节约一次取余运算。

然后创建一个二维数组answerArrayList，放入数组内的每个元素都是一个可以互相整除的数组。 以questionArray内的第一个元素（也就是最小的元素）创建一个数组作为第一个解放入answerArrayList。 这时这个数组相当于哨兵节点，后续代码就不需要考虑answerArrayList为空的情况了。

初始条件设计完了，以下就是暴力计算所有可以互相整除的数组的算法：

1. 从1开始遍历，每次从questionArray取出一个新的数字questionArray[i]，进行以下判断：
2. 记录当前answerArrayList的长度canPassAnswerNum；
3. 遍历answerArrayList内的元素，也就是目前可以互相整除的所有数字组合answerArray，针对answerArray做以下操作：
4. 遍历answerArray的每个元素answerArray[k]，当questionArray[i]不能整除answerArray[k]时，跳出循环；
5. 判断循环次数k的大小：
6. 如果k === answerArray.length，证明questionArray[i]可以被当前数组所有元素整除，将当前元素添加到answerArray；
7. 而如果k > 0，证明questionArray[i]可以被当前数组的一部分整除，以可以整除的部分加questionArray[i]创建一个新数组放入newAnswerArrayList，注意这里需要对newAnswerArrayList去重；
8. 如果k === 0，将canPassAnswerNum减1；
9. 对answerArray的遍历结束；
10. 将newAnswerArrayList拼接到answerArrayList内；
11. 如果canPassAnswerNum === 0，证明questionArray[i]和所有answerArray互质，需要单独用questionArray[i]创建一个数组放入answerArrayList；
12. 此时对questionArray[i]的遍历完毕。

按以上步骤遍历questionArray，最后可以得出所有可以互相整除的数组answerArrayList。 遍历answerArrayList，取出最长的数组返回即可。

代码如下：

var largestDivisibleSubset = function(nums) {

    const numsLength = nums.length;
    const questionArray = nums.sort((a, b) => a - b);
    let answerArrayList = [];

    answerArrayList.push([questionArray[0]]);

    for (let i = 1; i < numsLength; i++) {
        let newAnswerArrayList = [];
        let j = 0;
        let canPassAnswerNum = answerArrayList.length;
        for (; j < answerArrayList.length; j++) {
            const answerArray = answerArrayList[j];
            let k = 0;
            for (; k < answerArray.length; k++) {
                if (questionArray[i] % answerArray[k] !== 0) {
                    break;
                }
            }
            if (k === answerArray.length) {
                answerArray.push(questionArray[i]);
            } else if (k > 0) {
                const newAnsArray = answerArray.slice(0, k);
                newAnsArray.push(questionArray[i]);
                let l = 0;
                for (;l < newAnswerArrayList.length; l++) {
                    if (newAnswerArrayList[l].toString() === newAnsArray.toString()) {
                        break;
                    }
                }
                if (l === newAnswerArrayList.length) {
                    newAnswerArrayList.push(newAnsArray);
                }
            } else {
                canPassAnswerNum--
            }
        }
        answerArrayList = answerArrayList.concat(newAnswerArrayList);
        newAnswerArrayList = [];
        if (canPassAnswerNum === 0) {
            answerArrayList.push([questionArray[i]]);
        }
    }

    const answer = {
        index: 0,
        length: 0
    }

    answerArrayList.forEach((item, index) => {
        if (item.length > answer.length) {
            answer.index = index;
            answer.length = item.length;
        }
    });

    return answerArrayList[answer.index];
};

不难看出，这个算法无论时间复杂度还是空间复杂度都极高。 在 leetcode 上提交时也卡在了一个长度为635的数组上。 所以势必需要寻找更优秀的算法。

动态规划

利用动态规划解决这个问题的详细思路可以参看 leetcode 的解答 (opens new window)，这里只简要说明这道题的思路： 寻找最大整除子集，可以化简为寻找最大整除子集中的最大整数，再由最大整数可以反推出最大子集内的所有整数。 算法如下：

1. 首先还是将输入数组排序；
2. 声明一个等于当前数组长度的空数组 dp ；
3. 然后依次计算数组内的数字是可整除子集内的第几个数字，每次循环做的运算如下：
4. 只需要以当前数依次从大往小除以已遍历过的数字，第一个能整除的就是当前数字的所在的子集，记录dp[i]=dp[j] + 1；
5. 同时在循环中记录当前最大的dp[i]与i，为后续遍历求解做准备；
6. 遍历排序后的输入数组，取出每个可以整除最大值的元素，拼接出结果。

代码如下：

var largestDivisibleSubset = function(nums) {

    const numsLength = nums.length;
    const dp = new Array(numsLength).fill(1);
    const ansArr = [];
    const maxInfo = {
        dp: 1,
        index: 0
    }

    nums.sort((a, b) => a - b);

    for (let i = 1; i < numsLength; i++) {
        for(let j = i - 1; j >= 0; j--) {
            if (nums[i] % nums[j] === 0 && dp[j] > dp[i] - 1) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > maxInfo.dp) {
            maxInfo.dp = dp[i];
            maxInfo.index = i;
        }
    }

    for (let k = maxInfo.index; k >= 0; k--) {
        if (nums[maxInfo.index] % nums[k] === 0 && maxInfo.dp === dp[k]) {
            ansArr.unshift(nums[k]);
            maxInfo.dp--;
            maxInfo.index = k;
        }
    }

    return ansArr;
};

// Runtime: 148 ms, faster than 14.67% of JavaScript online submissions for Largest Divisible Subset.
// Memory Usage: 40.3 MB, less than 99.02% of JavaScript online submissions for Largest Divisible Subset.

上述答案消耗的时间还是与平均水平有差距，对比了一下优秀答案，有以下优化点：

• maxInfo 对象储存了 dp 属性，导致每次遍历时都需要多保存一个数值，其实只保存 index 就可以找到 dp 值了；
• 虽然不知道有没有性能上的优化，但优秀代码中创建数组使用的是Int16Array。

修改后代码如下：

var largestDivisibleSubset = function(nums) {

    const numsLength = nums.length;
    const dp = new Int16Array(numsLength).fill(1);
    const ansArr = [];

    let maxIndex = 0;

    nums.sort((a, b) => a - b);

    for (let i = 1; i < numsLength; i++) {
        for(let j = i - 1; j >= 0; j--) {
            if (nums[i] % nums[j] === 0 && dp[j] > dp[i] - 1) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > dp[maxIndex]) {
            maxIndex = i;
        }
    }

    let currentDp = dp[maxIndex];

    for (let k = maxIndex; k >= 0; k--) {
        if (nums[maxIndex] % nums[k] === 0 && currentDp === dp[k]) {
            ansArr.unshift(nums[k]);
            currentDp--;
            maxIndex = k;
        }
    }

    return ansArr;
};

// Runtime: 96 ms, faster than 85.33% of JavaScript online submissions for Largest Divisible Subset.
// Memory Usage: 40.7 MB, less than 94.62% of JavaScript online submissions for Largest Divisible Subset.

优化有效，本题作答完成。