Can any one share how you come up with your recurrence formula?


  • 0
    D
    This post is deleted!

  • 0

    @DPpanic

    • sort the array first to make it easier to consider next move
    • every pair of numbers in a set should be divisible by the larger one and now since it's sorted, so the larger one is the one with higher index
    • traversing the sorted array and record the maximal amount of the set ending with the current number is the key.

    when doing this, we should check if there are sub-sets available before for the current number (which can divide the current - which we can add the current to the subset to make a larger subset) and then update the max amount for the current number -

    • meantime to be able to collect the subsets later on, we should record the previous index of the smaller number and also we should update the global max till the end.

    A solution in C++ should be like this.

    class Solution {
    public:
        vector<int> largestDivisibleSubset(vector<int>& nums) 
        {
            int size = nums.size();
            if(!size) return vector<int>();
            sort(nums.begin(), nums.end());
            vector<pair<int, int>> maxWithIndex(1, make_pair(1, -1));
            int globalMax = 1, index = 0;
            for(int i = 1; i < size; ++i)
            {
                int maxCount = 1, preIndex = -1;
                for(int j = i-1; j >=0; --j)
                {
                    if(nums[i]%nums[j]==0 && maxWithIndex[j].first>=maxCount)
                        maxCount = maxWithIndex[j].first+1, preIndex = j;
                }
                maxWithIndex.emplace_back(maxCount, preIndex);
                if(maxCount > globalMax) globalMax = maxCount, index = i;
            }
            vector<int> v;
            for(int i = 0; i < globalMax; ++i, index = maxWithIndex[index].second) v.insert(v.begin(), nums[index]);
            return v;
        }
    };
    

Log in to reply
 

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