详细前请查看注释

参考代码：

class Solution {
public:
    /*
        性质：只要选出来的数相邻之间可以整除，则选出来的序列就可以两两整除！----> 整除具有传递性！
        类似最长上升子序列！
        状态表示：f[i]：表示前i个数中以a[i]结尾的整除序列的最大长度
        状态计算：f[i] = f[j] + 1  (j可取 1,2,3...i - 1 )
    */
    vector<int> largestDivisibleSubset(vector<int>& a) {
        int n = a.size();
        vector<int> f(n + 1), pre(n + 1);
        sort(a.begin(), a.end());
        int k = 0; // 记录最长序列的末尾下标
        for(int i = 0; i < n; i ++){
            f[i] = 1;
            for(int j = 0; j < i; j ++)
                if(a[i] % a[j] == 0){
                    if(f[i] < f[j] + 1){
                        f[i] = f[j] + 1;
                        pre[i] = j;
                    }
                }
            if(f[k] < f[i]) k = i;
        }
        // 获取最长整除序列路径；
        vector<int> res;
        while(true){
            res.push_back(a[k]);
            if(f[k] == 1) break;
            k = pre[k];
        }
        return res;
    }
};