Easy DP with path record, C++ code, O(n^2) time on worst case, O(n) space


  • 4

    the idea is using a bucket to record which nums can be the current longest sequence,
    and meantime using pair record the pre-num's id in its bucket, so we can get the result using it.

    see this case [1,2,3,4,5,6,7,24]

    at last it runs like this:

     1 | 2 | 4 | 24
       | 3 | 6 |
       | 5 |    
       | 7 |    
    

    code:

    vector<int> largestDivisibleSubset(vector<int>& nums) {
        vector<int> ret;
        int n = nums.size();
        if (!n) return ret;
        sort(nums.begin(), nums.end());
        vector<pair<int, int>> dp[n];
        int maxi = 0;
        dp[maxi].push_back(make_pair(nums[0], -1));
        for (int i = 1; i < n; ++i) {
            int j = maxi;
            while (j >= 0) {
                for (int id = 0; id < dp[j].size(); ++id) {
                    if (nums[i] % dp[j][id].first == 0) {
                        dp[j + 1].emplace_back(nums[i], id);
                        maxi = max(maxi, j + 1);
                        goto out_of_while;
                    }
                }
                --j;
            }
            dp[j + 1].emplace_back(nums[i], -1);
            out_of_while:;
        }
        int i = maxi, id = 0;
        while (i >= 0) {
            ret.push_back(dp[i][id].first);
            id = dp[i][id].second;
            --i;
        }
        return ret;
    }

Log in to reply
 

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