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]
找出最长的数组，数组中任取两个数，一个能被另一个整除。
var largestDivisibleSubset = function(nums) {
nums.sort((a,b) => a - b);
//T[i]代表以nums[i]开头的满足条件的数组的长度
//这个数组是递增的nums[i]是其中最小的元素
var T = [];
//生成结果数组用的
//parent[i]代表在结果数组中nums[i]的下一个在nums中的下标
var parent = [];
//最长的满足要求数组的长度
var m = 0;
//最长的满足要求数组的起始
var mi = 0;
//从最大的开始遍历数组
for(let i = nums.length - 1; i >= 0; --i)
{
//检测每一个比当前元素大的元素
for(let j = i; j < nums.length; ++j)
{
T[i] === undefined ? T[i] = 0 : 0;
T[j] === undefined ? T[j] = 0 : 0;
//如果大的数能除尽小的数，那代表以这个大的数起始的符合要求的数组中的元素都能除尽这个小的数
//这个小的数可以加到这个数组中了
//循环在比小的数大的数中找到最长的符合要求的数组
if(nums[j] % nums[i] === 0 && T[i] < 1 + T[j])
{
//更新当前元素起始的符合要求数组的长度
T[i] = 1 + T[j];
//跟新当前元素后面的元素下标
parent[i] = j;
if(T[i] > m)
{
//更新最长长度
m = T[i];
//更新起始点
mi = i;
}
}
}
}
var ret = [];
//根据起始点和parent重构结果数组
for(let i = 0; i < m; ++i)
{
ret.push(nums[mi]);
mi = parent[mi];
}
return ret;
};
