0368. 最大整除子集【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

给你一个由 无重复 正整数组成的集合 nums，请你找出并返回其中最大的整除子集 answer，子集中每一元素对 (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^9
• nums 中的所有整数 互不相同

2. 🎯 s.1 - 动态规划

c

int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }

int* largestDivisibleSubset(int* nums, int numsSize, int* returnSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int* dp = (int*)malloc(sizeof(int) * numsSize);
    int* parent = (int*)malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; i++) { dp[i] = 1; parent[i] = -1; }
    int maxIdx = 0;
    for (int i = 1; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        if (dp[i] > dp[maxIdx]) maxIdx = i;
    }
    *returnSize = dp[maxIdx];
    int* res = (int*)malloc(sizeof(int) * (*returnSize));
    int idx = *returnSize - 1;
    for (int i = maxIdx; i != -1; i = parent[i]) res[idx--] = nums[i];
    free(dp); free(parent);
    return res;
}

js

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var largestDivisibleSubset = function (nums) {
  nums.sort((a, b) => a - b)
  const n = nums.length
  const dp = new Array(n).fill(1)
  const parent = new Array(n).fill(-1)
  let maxIdx = 0
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] % nums[j] === 0 && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1
        parent[i] = j
      }
    }
    if (dp[i] > dp[maxIdx]) maxIdx = i
  }
  const res = []
  for (let i = maxIdx; i !== -1; i = parent[i]) res.push(nums[i])
  return res.reverse()
}

py

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        dp = [1] * n
        parent = [-1] * n
        max_idx = 0
        for i in range(1, n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    parent[i] = j
            if dp[i] > dp[max_idx]:
                max_idx = i
        res = []
        i = max_idx
        while i != -1:
            res.append(nums[i])
            i = parent[i]
        return res[::-1]

• 时间复杂度：$O(n^2)$，其中 $n$ 是数组长度
• 空间复杂度：$O(n)$

算法思路：

• 排序后，$dp[i]$ 表示以 $nums[i]$ 结尾的最大整除子集长度
• 若 $nums[i]\mathrm{\%}nums[j]=0$ 且 $dp[j]+1>dp[i]$，则转移
• 用 parent 数组回溯路径构造结果