【leetcode刷题】T169-最大整除子集

示例 1:
输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)

示例 2:
输入: [1,2,4,8]
输出: [1,2,4,8]

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums) < 1:
            return []
        nums.sort()
        dp = [1] * len(nums)
        parent = [i for i in range(len(nums))]
        for i, n in enumerate(nums):
            for j in range(i-1, -1, -1):
                # dp[i] = max(dp[i], dp[j] + 1) 
                if nums[i] % nums[j] == 0:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        parent[i] = j

        max0 = max(dp)
        p = dp.index(max0)
        res = []
        while True:
            res.append(nums[p])
            if p == parent[p]:
                break
            p = parent[p]
        return res

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        vector<int> res;
        if(nums.size() < 1)
            return res;
        sort(nums.begin(), nums.end());
        // 构建dp数组、parent数组
        vector<int> dp(nums.size(), 1);
        vector<int> parent(nums.size(), 0);
        for(int i=1; i<nums.size(); i++){
            parent[i] = i;
            for(int j=i-1; j>=0; j--){
                if(nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
        }
        // 最大值下标
        int p = 0;
        for(int i=0; i<dp.size(); i++){
            if(dp[p] < dp[i])
                p = i;
        }
        // 最长序列
        while(true){
            res.push_back(nums[p]);
            if(p == parent[p])
                break;
            p = parent[p];
        }
        return res;
    }
};