C++ O(N^2) solution, 56ms


  • 1
    I
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if (nums.empty()) return vector<int>();
        sort(nums.begin(), nums.end());
        vector<pair<int, int>> dp(nums.size(), make_pair(1, -1));
        int globalLargest = 1, globalLargestIdx = 0;
        for (int i = 1; i < nums.size(); i++) {
            int largest = 1, parentIdx = -1;
            for (int j = i - 1; j > - 1; j--) {
                if (nums[i] % nums[j] == 0) {
                    if (dp[j].first + 1 > largest) {
                        parentIdx = j;
                        largest = dp[j].first + 1;
                    }
                }
            }
            dp[i].first = largest;
            dp[i].second = parentIdx;
            if (largest > globalLargest) {
                globalLargestIdx = i;
                globalLargest = largest;
            }
        }
        vector<int> ret;
        for (int idx = globalLargestIdx; idx != -1; idx = dp[idx].second) {
            ret.push_back(nums[idx]);
        }
        return ret;
    }

  • 0

    @Irving_cl Very clean solution, perhaps if you can modify your last collecting process as follows, the result can be more tidy, in an ascending order.

    ret.insert(ret.begin(), nums[idx]);

    Thanks for sharing!


  • 0
    I

    @LHearen Thank you for your advice~


Log in to reply
 

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