O(n^2) c++ solution


  • 0
    W
    class Solution {
    public:
        typedef vector<int> vct;
        vct largestDivisibleSubset(vct& nums) {
            int len = nums.size();
            vct ans;
            if (len == 0) {
                return ans;
            }
            vct t(len, 1);  // max size of set whose max element is nums[i]
            vct p(len, -1); //index backtrace to construct the max size set
            int mi = 0; // record the max index
            sort(nums.begin(), nums.end());
            for (int i=0; i<len; i++) {
                for (int j=0; j<i; j++) {
                    if (nums[i] % nums[j] == 0) {
                        if (t[j] + 1 > t[i]) {
                            p[i] = j;
                            t[i] = t[j] + 1;
                            if (t[mi] < t[i]) {
                                mi = i;
                            }
                        }
                    }
                }
            }
            while (mi > -1) {
                ans.push_back(nums[mi]);
                mi = p[mi];
            }
            return ans;
        }
    };
    

Log in to reply
 

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