给了一个数组，求数组中最大的子数组，要求这个子数组中的每两个数都有整除关系。
看到这样的题，第一反应是 DP 。给了数组，又不像贪心，那它很可能是 DP。
假设 $a,\; b,\; c$ 三个数可以算作一个子数组。因为一个数被比它小的数除，才有整除的可能，$a,\; b,\; c$ 一定有大小关系，假设 $a < b < c$，那么一定是 $ b\; \% \;a = 0, \; c\; \% \;a = 0, \; c\; \% \; b = 0 $ 。再想，当 $ c\; \% \;b = 0$， $ b\; \% \;a = 0$ 时，$ c\; \% \;a $ 一定等于 0 。同时，这些数一定是某个等比数列中的一部分（不一定连续）。
根据上面的分析，我们首先对原始数据排序，大的数去除小的数，如果整除，加入某个集合中，继续向后扫描，更大的数，只需要去对每个集合中最后一个数判断就好，如果新的数能被某个集合中最大的数整除，那么一定能被这个集合中的其他数整除。
这样做，空间复杂度很高，我们还可以通过记录前一个数的索引的方法优化，使用一个 $parent$ 数组记录当前数可以整除前面最大的某个集合中的最大的数的索引，这样遍历完毕后，我们可以根据每个数的前一个数来回溯构建答案。
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
const int n = nums.size();
vector<int> lens(n);
int cur_len = 0, last = 0;
vector<int> parent(n);
sort(nums.begin(), nums.end());
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] % nums[j] == 0) {
if (lens[i] < lens[j] + 1) {
lens[i] = lens[j] + 1;
parent[i] = j;
}
}
}
if (lens[i] > cur_len) {
cur_len = lens[i];
last = i;
}
}
vector<int> res;
res.reserve(cur_len);
for (int i = 0; i <= cur_len; ++i) {
res.emplace_back(nums[last]);
last = parent[last];
}
return res;
}
};