leetcode 368. Largest Divisible Subset
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:
Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.
Example 1:
Input: [1,2,3] Output: [1,2] (of course, [1,3] will also be ok) Example 2: Input: [1,2,4,8] Output: [1,2,4,8]
题目大意：给定一个无重复的正整数集合，找出最大的整除子集。子集中任意一对($S_i$, $S_j$)都满足： $S_i \% S_j = 0$ 或 $S_i \% S_j = 0$。
如果有多个子集符合条件，返回其中一个即可。
基本思路：列出集合所有的子集，共有$2^n$个，再进行判断，时间复杂度为O($C_n^2 \times 2^n$)，其中$n$为集合元素个数。
由于返回的子集需要满足子集中任意一对($S_i$, $S_j$)有 $S_i \% S_j = 0$ 或 $S_i \% S_j = 0$，为了减少考虑次数，可以考虑先对原始集合排序，这样只要考虑$S_i \% S_j$(i > j)。
排好序之后的做法基本和最长递增子序列(https://leetcode.com/problems/longest-increasing-subsequence/)一致。
做法： 1、对集合数组nums排序，长度为len=nums.size();
2、定义一个和nums等长的数组dp[len], 其中dp[i]表示nums[0,..., i]符合条件的最大子集的长度。dp[j] = max(dp[i]) + 1 (i = 0, 1, ..., j - 1. 且nums[j] % nums[i] = 0)。初始化为1.
3、定义一个和nums等长的索引数组index[len]。index[i]表示以nums[i]结尾的满足条件的最大子集，子集元素nums[i]的前一个元素在原数组中的索引（下标）。初始化为-1.
4、根据dp数组，知道满足条件的最大子集的最后一个元素的索引（下标），然后根据index数组，推出前面所有的元素。
注：这种做法可以求出所有满足条件的最大子集。
C++代码：
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
int len = nums.size();
if (len == 0) //数组长度为0，直接返回空集。
return {};
vector<int> dp(len, 1);
vector<int> previous_index(len, -1);
int max_ind = 0; //记录最长子集的末尾元素索引值
sort(nums.begin(), nums.end()); //按照从小到大排序
for (int i = 1; i < len; ++i) { //外层循环控制以i结尾的数组
for (int j = 0; j < i; ++j) { //内层循环计算dp[i]
if ((nums[i] % nums[j] == 0) && (dp[j] >= dp[i])) {
dp[i] = dp[j] + 1;
previous_index[i] = j;
}
}
if (dp[i] > dp[max_ind]) {
max_ind = i;
}
}
vector<int> answer(dp[max_ind], 0); //dp[max_ind]即为最长子集的长度
for (int t = max_ind, i = 0; t >= 0; ++i) {
answer[i] = nums[t];
t = previous_index[t];
}
return answer;
}
};时间复杂度：$O(nlogn) + O(n^2)$