C++ Solution using DP


  • 3
    F
    class Solution {
    public:
        vector<int> largestDivisibleSubset(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> result(nums.size());
            vector<int> ret;
            for (int i = 0;i < nums.size();++i) {
                for (int j = 0;j < i;++j) {
                    if (nums[i] % nums[j] == 0 && result[j].size() > result[i].size()) {
                        result[i] = result[j];
                    }
                }
                result[i].push_back(nums[i]);
                if (ret.size() < result[i].size()) ret = result[i];
            }
            return ret;
        }
    };
    

    The total runtime is O(n^2). If any more efficient algorithm, welcome to discuss.


  • 0
    S

    Clean solution and easy to read.


  • 1
    J

    Considering you copy the vector in the loop, it's larger than O(n^2) if the array is long.

    I adjust the code a little bit to avoid copying vectors:
    class Solution {
    public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<int> ptr(nums.size());
    vector<int> length(nums.size());
    vector<int> ret;

        int maxLength = -1;
        int head = -1;
        
        for (int i = 0;i < nums.size();++i) {
            ptr[i] = -1;
            length[i] = 1;
            for (int j = 0;j < i;++j) {
                if (nums[i] % nums[j] == 0 && length[j] + 1 > length[i]) {
                    ptr[i] = j;
                    length[i] = length[j] + 1;
                }
            }
            if (maxLength < length[i]) {
                maxLength = length[i];
                head = i;
            }
        }
        
        while (head != -1) {
            ret.push_back(nums[head]);
            head = ptr[head];
        }
        return ret;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.