368.最大整除子集

【LetMeFly】368.最大整除子集

力扣题目链接：https://leetcode.cn/problems/largest-divisible-subset/

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

方法一：动态规划 + traceback

上来先给nums从小到大排个序，这没什么好说的。

排完序后：

step1. 动态规划求得以nums[i]结尾的最长“递增倍数串”的长度

数组中各个元素各不相同，想要“互为倍数”，就要“大的 是 小的 的 整数倍”

假如一个“互为倍数”数组中已经有了两个元素5, 15，那么想要往这个数组中再添加一个元素的话，新的元素就要是15的整数倍。这是因为我们“上来就给nums从小到大排了个序”。

如果一个数是15的整数倍，那么它一定是5的整数倍。

这不，动态规划的转移方程就来了？

$dp[i] = \max{dp[i], dp[j] + 1}$，其中$j < i \wedge nums[i] % nums[j] = 0$

说人话就是，怎么求$dp[i]$呢？在所有的小于$i$的下标中，如果某个数能被$nums[i]$整除（假设为第$j$个数），那么$dp[i] = \max(dp[i],dp[j]+1)$

因为$nums[i]$是$nums[j]$的倍数的话，$num[i]$可以添加到以$nums[j]$结尾的“递增互为倍数集合”中。

这样，两层循环就能求出$dp$数组的值，其中$dp[i]$表示以$nums[i]$结尾的“递增互为倍数集合”的最大大小。

vector<int> dp(n, 1);
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] % nums[j] == 0) {
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}

step2. 根据“递增倍数串”后面的元素倒推出前面的元素

题目问的不是“互为倍数集合的最大元素个数”，而是要你把这个集合给出来。

但是这就不难了。我们在step1中动态规划求“最大大小”时，可以额外记录一下：

1. 最大大小是多少
2. 最大的集合中，最大的数有多大

只需要做如下更改：

vector<int> dp(n, 1);
int maxLength = 0;
int maxVal = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] % nums[j] == 0) {
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    if (dp[i] > maxLength) {
        maxLength = dp[i];
        maxVal = nums[i];
    }
}

这样，我们就知道了“答案集合的最大数”、“答案集合的大小”

假如答案集合是[5, 15, 30]，那么我们知道的是：

1. 答案中的最大数是30
2. 答案集合的大小是3

同时我们也知道了整个dp数组，其中5对应的dp值是1，15对应的dp值是2，30对应的dp值是3

因此我们可以从后往前遍历一遍数组（从大到小）

如果遇到某个数对应的dp值恰好等于“maxLength”，并且这个数能被“maxVal”整除，那么就说明这个数是集合中的一个数

更新maxLength为maxLength - 1，更新maxVal为这个数。

vector<int> ans(maxLength);
for (int i = n - 1; i >= 0; i--) {
    if (maxVal % nums[i] == 0 && dp[i] == maxLength) {
        ans[--maxLength] = nums[i];
        maxVal = nums[i];
        if (!maxLength)
            break;
    }
}

同样以答案集合[5, 15, 30]为例：

1. maxLength = 3, maxVal = 30，找到30时，发现30对应的dp值恰好为3，且30能被30整除。因此我们得到了答案集合中的30，并将maxLength更新为2，将maxVal更新为30
2. maxLength = 2, maxVal = 30，找到15时，发现15对应的dp值恰好为2，且30能被15整除。因此我们得到了答案集合中的15，并将maxLength更新为1，将maxVal更新为15
3. maxLength = 1, maxVal = 15，找到5时，发现15对应的dp值恰好为1，且15能被5整除。因此我们得到了答案集合中的5，并将maxLength更新为.，将maxVal更新为5

寻找结束。

• 时间复杂度$O(n^2)$，其中$n$是$nums$的大小
• 空间复杂度$O(n)$

AC代码

C++

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> dp(n, 1);
        int maxLength = 0;
        int maxVal = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            if (dp[i] > maxLength) {
                maxLength = dp[i];
                maxVal = nums[i];
            }
        }
        vector<int> ans(maxLength);
        for (int i = n - 1; i >= 0; i--) {
            if (maxVal % nums[i] == 0 && dp[i] == maxLength) {
                ans[--maxLength] = nums[i];
                maxVal = nums[i];
                if (!maxLength)
                    break;
            }
        }
        return ans;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127210616