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]
找出最長(zhǎng)的數(shù)組，數(shù)組中任取兩個(gè)數(shù)枢劝，一個(gè)能被另一個(gè)整除您旁。
var largestDivisibleSubset = function(nums) {
nums.sort((a,b) => a - b);
//T[i]代表以nums[i]開頭的滿足條件的數(shù)組的長(zhǎng)度
//這個(gè)數(shù)組是遞增的nums[i]是其中最小的元素
var T = [];
//生成結(jié)果數(shù)組用的
//parent[i]代表在結(jié)果數(shù)組中nums[i]的下一個(gè)在nums中的下標(biāo)
var parent = [];
//最長(zhǎng)的滿足要求數(shù)組的長(zhǎng)度
var m = 0;
//最長(zhǎng)的滿足要求數(shù)組的起始
var mi = 0;
//從最大的開始遍歷數(shù)組
for(let i = nums.length - 1; i >= 0; --i)
{
//檢測(cè)每一個(gè)比當(dāng)前元素大的元素
for(let j = i; j < nums.length; ++j)
{
T[i] === undefined ? T[i] = 0 : 0;
T[j] === undefined ? T[j] = 0 : 0;
//如果大的數(shù)能除盡小的數(shù)军掂，那代表以這個(gè)大的數(shù)起始的符合要求的數(shù)組中的元素都能除盡這個(gè)小的數(shù)
//這個(gè)小的數(shù)可以加到這個(gè)數(shù)組中了
//循環(huán)在比小的數(shù)大的數(shù)中找到最長(zhǎng)的符合要求的數(shù)組
if(nums[j] % nums[i] === 0 && T[i] < 1 + T[j])
{
//更新當(dāng)前元素起始的符合要求數(shù)組的長(zhǎng)度
T[i] = 1 + T[j];
//跟新當(dāng)前元素后面的元素下標(biāo)
parent[i] = j;
if(T[i] > m)
{
//更新最長(zhǎng)長(zhǎng)度
m = T[i];
//更新起始點(diǎn)
mi = i;
}
}
}
}
var ret = [];
//根據(jù)起始點(diǎn)和parent重構(gòu)結(jié)果數(shù)組
for(let i = 0; i < m; ++i)
{
ret.push(nums[mi]);
mi = parent[mi];
}
return ret;
};
