368. 最大整除子集

发表于 分类于 阅读次数： Waline： 本文字数： 853 阅读时长 ≈ 3 分钟

考点

  • LIS
  • 整除的链式特性

思路

一、问题描述（形式化）

给定一个由 互不相同的正整数 组成的集合 \[ S = \{a_1, a_2, \dots, a_n\} \] 要求找出一个最大规模的子集 \[ T \subseteq S \] 使得对任意 \(x, y \in T\)，满足以下二者之一： \[ x \mid y \quad \text{或} \quad y \mid x \] 输出任意一个满足条件的最大子集。

二、核心数学定理（DP 可行性的根源）

定理 1（整除关系的传递性）

对正整数 \(a,b,c\)，若 \[ a \mid b \quad \text{且} \quad b \mid c \] 则必有 \[ a \mid c \] 证明： 由 \(a \mid b\)，存在整数 \(k_1\) 使 \(b = a k_1\)； 由 \(b \mid c\)，存在整数 \(k_2\) 使 \(c = b k_2 = a(k_1 k_2)\)。 故 \(a \mid c\)，证毕。

推论（链式结构充要性）

若一个集合按升序排列为 \[ b_1 < b_2 < \dots < b_k \] 并满足相邻元素 \[ b_i \mid b_{i+1} \quad (1 \le i < k) \] 则该集合中 任意两元素都满足整除关系。

也就是说： 只要子集形成一条“整除链”，就自动满足题目要求。

三、问题转化

  1. 将数组按升序排序： \[ a_1 \le a_2 \le \dots \le a_n \]

  2. 原问题转化为：

在排序后的数组中，寻找一条最长的下标递增序列 \[ i_1 < i_2 < \dots < i_k \] 使得 \[ a_{i_1} \mid a_{i_2} \mid \dots \mid a_{i_k} \]

这与 最长递增子序列（LIS） 在形式上完全一致，只是：

  • “<” 被替换为 “\(\mid\)”

四、动态规划建模

1. 状态定义

设排序后数组为 \(a[1..n]\)。

  • \(f[i]\)：以 \(a[i]\) 作为最大元素（末尾）时，能够形成的最大整除子集的长度
  • \(pre[i]\)：在该最优方案中，\(a[i]\) 的直接前驱元素下标

2. 初始条件

任意单个元素都能构成合法子集，因此： \[ f[i] = 1 \quad (1 \le i \le n) \] 若没有前驱，则： \[ pre[i] = 0 \]

3. 状态转移方程

对每一个 \(i\)，枚举所有 \(j < i\)：

若 \[ a[i] \bmod a[j] = 0 \] 则可以将 \(a[i]\) 接到以 \(a[j]\) 结尾的整除链后面。

转移方程为： \[ f[i] = \max\left(f[i],\; f[j] + 1\right) \] 若更新发生，则： \[ pre[i] = j \]

4. 正确性说明（关键）

由于整除关系具有传递性：

  • 若 \(a[j]\) 是某条整除链的末尾
  • 且 \(a[j] \mid a[i]\)

则链中所有更小的元素都必然整除 \(a[i]\)， 因此 只需检查链的末尾元素即可，无需检查整个子集。

五、答案的确定与恢复

  1. 在所有状态中找到最大值： \[ \text{mx} = \max_{1 \le i \le n} f[i] \]

  2. 设该最大值对应的下标为 idx，则：

    • idx 是最大整除子集的最后一个元素

  3. 通过 pre[idx] 不断向前回溯，直到 0，即可恢复整条链。

六、时间与空间复杂度分析

  • 排序：\(O(n \log n)\)
  • DP 转移：双重循环，\(O(n^2)\)
  • 回溯：\(O(n)\)

总体复杂度： \[ O(n^2) \] 空间复杂度： \[ O(n) \] 在 \(n \le 1000\) 的约束下完全可行。

七、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    static const int maxn = 1e3 + 5;
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int f[maxn], pre[maxn];
        memset(pre, 0, sizeof(pre));
        int n = nums.size(), mx_len = 0, idx;
        for (int i = 1; i <= n; ++i) {
            f[i] = 1;
            for (int j = i - 1; j >= 1; --j) {
                if (nums[i - 1] % nums[j - 1] == 0 && f[j] + 1 > f[i]) {
                    f[i] = f[j] + 1, pre[i] = j;
                }
            }
            if (f[i] > mx_len)
                idx = i, mx_len = f[i];
        }
        vector<int> ans;
        while (idx) {
            ans.push_back(nums[idx - 1]);
            idx = pre[idx];
        }
        return ans;
    }
};