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]

这题的意思是给定一个数组，找出一个最长的子串，它们各自都能被别的数整除。

这题一开始没理解什么意思，比较晦涩。后来仔细想了一下，小的数除以大的数肯定不能整除，所以我们可以一开始将数组做一次升序排列，这样我们只要看一下后一个数能否被前一个数整除就可以了，反着就不用考虑了。

接下来，这题可以使用Dynamic programing来解题。我们可以这样子想，我们从尾巴处开始找最长的子串，首先只有末尾的一个数字，则最长子串肯定就是它了，所以目前的最长子串就是它。

然后，我们开始将第二大的数字和它作比较，假设能整除，那么最长子串的长度就变成2了。

我们定义一个dp数组，长度为数组长度，dp[i]表示的是最大数为nums[i]的最长子串长度。当我们将一个比它们都小的数和别的dp[j]比较的时候，假设dp[j]+1的值大于dp[i]的值，就说明目前最长的子串可以更新了，我们同时要保存目前最大dp[i]的值以及索引，还有对应的它连接的别的子串的索引。

下面是代码：

vector<int> largestDivisibleSubset(vector<int>& nums) {
        // Sort the array
        std::sort(nums.begin(), nums.end());
        vector<int> dp(nums.size(), 0);
        vector<int> parent(nums.size(), 0);
        int mx = 0, mi = 0;

        for (int i = nums.size() - 1; i >= 0; i--) {
            for (int j = i; j < nums.size(); j++) {
                if (nums[j] % nums[i] == 0 &&
                    dp[j] + 1 > dp[i]) {
                        // We can add the nums[i] to the front of the nums[j] subset
                        dp[i] = dp[j] + 1;
                        parent[i] = j;
                        if (dp[i] > mx) {
                            mx = dp[i];
                            mi = i;
                        }
                }
            }
        }

        vector<int> res(mx, 0);
        for (int i = 0; i < mx; i++) {
            res[i] = nums[mi];
            mi = parent[mi];
        }
        return res;
    }