LeetCode 368. Largest Divisible Subset

思路：
想到一个词叫“传递性”，在这边应该也适用。就是如果b%a==0，然后c%b==0，那么肯定有c%a==0. 按照这个方法来构造一个集合就可以了，应该是动态规划的思想，results[i]保存包含数组元素nums[i]的最佳集合，构建集合的时候，首先从之前的results[j] (j=0…i-1)里面找到能够“传递”过来的集合(nums[i]%nums[i]==0)选作最佳（相当于找到c%b==0，当然这里的b是之前results[j]里面的最大元素，即nums[j]）然后加上本身的nums[i]就构成了到第i个元素为止的最佳集合，如此继续…
时间复杂度应该是O(n^2)

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if(nums.empty())
            return nums;
        sort(nums.begin(), nums.end());
        int bestIndex = 0;
        vector<vector<int>> results(nums.size());
        for(int i=0; i<nums.size(); i++){
            for(int j=0; j<i; j++){
                //nums[j] < nums[i]
                if(nums[i]%nums[j]==0 &&
                    results[i].size() < results[j].size())
                    results[i] = results[j];
            }
            results[i].push_back(nums[i]);
            if(results[bestIndex].size() < results[i].size())
                bestIndex = i;
        }
        return results[bestIndex];
    }
};