What is the main pattern used in Largest Divisible Subset?

The problem uses state transition dynamic programming to build up subsets based on previous valid divisible elements.

Do I need to sort the array first?

Yes, sorting ensures that every element considered for extension can only divide or be divided by smaller previous elements, simplifying DP transitions.

Can multiple correct outputs exist?

Yes, if there are multiple largest subsets satisfying divisibility, any one of them can be returned.

What is the time complexity of this approach?

The time complexity is O(n^2) because for each element, you may need to check all prior elements for divisibility.

How does GhostInterview handle subset reconstruction?

GhostInterview guides through tracing the prev array from the maximum dp index to reconstruct the largest divisible subset accurately.

#368

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最大整除子集

给你一个由无重复正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足： answer[i] % answer[j] == 0 ，或 answer[j] % answer[i] == 0 如果存在…

数组数学动态规划排序

题目描述

给你一个由 无重复 正整数组成的集合 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⁹
nums 中的所有整数 互不相同

lightbulb

解题思路

方法一：排序 + 动态规划

我们先对数组进行排序，这样可以保证对于任意的 $i \lt j$ ，如果 $nums[i]$ 可以整除 $nums[j]$ ，那么 $nums[i]$ 一定在 $nums[j]$ 的左边。

接下来，我们定义 $f[i]$ 表示以 $nums[i]$ 为最大元素的最大整除子集的大小，初始时 $f[i]=1$ 。

对于每一个 $i$ ，我们从左往右枚举 $j$ ，如果 $nums[i]$ 可以被 $nums[j]$ 整除，那么 $f[i]$ 可以从 $f[j]$ 转移而来，我们更新 $f[i]=max(f[i], f[j]+1)$ 。过程中，我们记录 $f[i]$ 的最大值的下标 $k$ 以及对应的子集大小 $m$ 。

最后，我们从 $k$ 开始倒序遍历，如果 $nums[k]$ 可以被 $nums[i]$ 整除，且 $f[i]=m$ ，那么 $nums[i]$ 就是一个整除子集的元素，我们将 $nums[i]$ 加入答案，并将 $m$ 减 $1$ ，同时更新 $k=i$ 。继续倒序遍历，直到 $m=0$ 。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        f = [1] * n
        k = 0
        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    f[i] = max(f[i], f[j] + 1)
            if f[k] < f[i]:
                k = i
        m = f[k]
        i = k
        ans = []
        while m:
            if nums[k] % nums[i] == 0 and f[i] == m:
                ans.append(nums[i])
                k, m = i, m - 1
            i -= 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n^2) due to the nested iteration for each element to check divisibility against prior elements. Space complexity is O(n) for the dp and prev arrays storing subset lengths and backtracking information.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks about efficient subset building beyond brute force.
question_mark
Wants you to recognize the dynamic programming state transition pattern.
question_mark
May probe alternative reconstruction methods and edge cases.

warning

常见陷阱

外企场景

error
Forgetting to sort nums can break the divisibility chain.
error
Incorrectly updating dp without checking all previous divisible elements.
error
Failing to reconstruct the subset using prev pointers after computing dp.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return all largest divisible subsets if multiple exist.
arrow_right_alt
Handle negative integers or zero with adjusted divisibility rules.
arrow_right_alt
Optimize for space using only a single array with backtracking reconstruction.

help

常见问题

外企场景

继续练习

#1363 形成三的最大倍数 #354 俄罗斯套娃信封问题 #435 无重叠区间