Link:
题目要求
给你一个由无重复正整数组成的集合nums，请你找出并返回其中最大的整除子集answer，子集中每一元素对(answer[i], answer[j])都应当满足：
answer[i] % answer[j] == 0，或
answer[j] % answer[i] == 0如果存在多个有效解子集，返回其中任何一个均可。
核心算法和原理
- 这类问题属于「相邻元素有约束，计算子序列最大长度（最优解）」，同LIS
- dp数组含义：
dp[i]表示「以第i个元素结尾的满足要求的子序列长度」，同时再记录一个_from来记录最优解的路径
- 状态转移方程：
- key point：剪枝方法（搬用0x3f大佬的题解）
代码
class Solution { public: vector<int> largestDivisibleSubset(vector<int>& nums) { ranges::sort(nums); int n = nums.size(); int maxI = 0, maxF = 0; unsigned maxNum = nums[n - 1]; vector<int> dp(n, 0), _from(n + 1, -1); // 维护一个有效的 可遍历index 集合 // 通过 当前最优解对应的nums[i](nums[maxI])、nums最大值(maxNum)和 // 最优解(maxF)，判断可遍历index里哪些依然可以成为「产生最优解的候选项」 vector<int> validIdx{}; for (int i = 0; i < n; i++) { for (int j : validIdx) { if (nums[i] % nums[j] == 0 && dp[j] > dp[i]) { dp[i] = dp[j]; _from[i] = j; // cout << "it: " << i << " " << _from[i] << endl; } } // valid idx dp[i]++; if (dp[i] > dp[maxI]) { maxI = i; maxF = dp[i]; vector<int> newValidIdx; for (int idx : validIdx) { if (dp[idx] + bit_width(maxNum / nums[idx]) - 1 > maxF) { newValidIdx.push_back(idx); } } validIdx = std::move(newValidIdx); } // 对i也要判断是否能加入validIdx if (dp[i] + bit_width(maxNum / nums[i]) - 1 > maxF) { validIdx.push_back(i); } } vector<int> path; for (int x = maxI; x != -1; x = _from[x]) { // cout << x << " " << _from[x] << endl; path.push_back(nums[x]); } return path; } };