368.最大整除子集

链接：368.最大整除子集
难度：Medium
标签：数组、数学、动态规划、排序
简介：给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer。

题解 1 - typescript

• 编辑时间：2021-04-23
• 执行用时：124ms
• 内存消耗：41MB
• 编程语言：typescript
• 解法介绍：动态规划。

function largestDivisibleSubset(nums: number[]): number[] {
  nums.sort((a, b) => a - b);
  const len = nums.length;
  let maxSize = 1;
  let maxVal = nums[0];
  const dp = new Array(len).fill(1);
  for (let i = 1; i < len; i++) {
    const num = nums[i];
    for (let j = 0; j < i; j++) {
      if (num % nums[j] === 0) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
    if (dp[i] > maxSize) {
      maxSize = dp[i];
      maxVal = num;
    }
  }
  const ans: number[] = [];
  for (let i = len - 1; i >= 0; i--) {
    const num = nums[i];
    if (dp[i] === maxSize && maxVal % num === 0) {
      ans.unshift(num);
      maxSize--;
      maxVal = num;
    }
  }
  return ans;
}