368. Largest Divisible Subset

[Tcdian]

368. Largest Divisible Subset

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

如果有多个目标子集，返回其中任何一个均可。

Example 1

Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)

Example 2

Input: [1,2,4,8]
Output: [1,2,4,8]

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var largestDivisibleSubset = function(nums) {
    if (nums.length === 0) {
        return [];
    }
    const dp = new Array(nums.length).fill(1);
    const track = new Array(nums.length).fill(-1);
    let maxCount = 0;
    let trackEnd = 0;
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] % nums[j] === 0 && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                track[i] = j;
                if (maxCount < dp[i]) {
                    maxCount = dp[i];
                    trackEnd = i;
                }
            }
        }
    }
    const result = [];
    while(trackEnd !== -1) {
        result.unshift(nums[trackEnd]);
        trackEnd = track[trackEnd];
    }
    return result;
};

• TypeScript Solution

function largestDivisibleSubset(nums: number[]): number[] {
    if (nums.length === 0) {
        return [];
    }
    const dp: number[] = new Array(nums.length).fill(1);
    const track: number[] = new Array(nums.length).fill(-1);
    let maxCount = 0;
    let trackEnd = 0;
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] % nums[j] === 0 && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                track[i] = j;
                if (maxCount < dp[i]) {
                    maxCount = dp[i];
                    trackEnd = i;
                }
            }
        }
    }
    const result: number[] = [];
    while(trackEnd !== -1) {
        result.unshift(nums[trackEnd]);
        trackEnd = track[trackEnd];
    }
    return result;
};