20 lines C++ O(n^2) solution


  • 1
    class Solution {
    public:
        vector<int> largestDivisibleSubset(vector<int>& nums) {
            if (nums.size() <= 1) return nums;
            sort(nums.begin(), nums.end());
            int maxLen = 1, maxIndx = 0;
            vector<pair<int, int>> temp(nums.size(), make_pair(1, -1));
            for (int i = 1; i < nums.size(); ++i) 
                for (int j = 0; j < i; ++j) 
                    if (nums[i] % nums[j] == 0 && temp[i].first < temp[j].first + 1) {
                        temp[i].first = temp[j].first + 1;
                        temp[i].second = j;
                        if (maxLen < temp[i].first) {
                            maxLen = temp[i].first;
                            maxIndx = i;
                        }
                    }
            vector<int> out;
            for ( ; maxIndx != -1; maxIndx = temp[maxIndx].second) out.push_back(nums[maxIndx]);
            return out;
        }
    };
    

    Similar to other solutions, just a little bit shorter :/


Log in to reply
 

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