LeetCode368(2021.4.23)

LC368. 最大整除子集

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> f(n, 0);
        vector<int> g(n ,0);
        for(int i = 0; i < n; i++) {
            int len = 1, prev = i;
            for(int j = 0; j < i; j++) {
                if(nums[i] % nums[j] == 0) {
                    if(f[j] + 1 > len) {
                        len = f[j] + 1;
                        prev = j;
                    }
                }
            }
            f[i] = len;
            g[i] = prev;
        }
        int idx = max_element(f.begin(), f.end()) - f.begin();
        int max = f[idx];
        vector<int> ans;
        while(ans.size() != max) {
            ans.push_back(nums[idx]);
            idx = g[idx];
        }
        return ans;
    }
};

发表评论