C++ DP solution


  • 0
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if (nums.empty())
    	return vector<int>();
        sort(nums.begin(), nums.end());
        vector<int> memo(nums.size(), 1);
        int maxDivisibleSubsetSize = 1, largestElementIdx = 0;
        // memo[i] represents the size of the max divisible subset whose largest element is nums[i]
        for (int i = 1; i < nums.size(); i++) {
        	for (int j = i - 1; j >= 0; j--) {
        		if (nums[i] % nums[j] == 0) {
        			memo[i] = max(memo[i], memo[j] + 1);
        			if (memo[i] > maxDivisibleSubsetSize) {
        				maxDivisibleSubsetSize = memo[i];
        				largestElementIdx = i;
        			}
        		}
        	}
        }
        // reconstruct the max divisible subset from memo
        // We can deduct an element nums[i] is in the max subset if 
        // it can divide the element we just added to the max subset (the smallest element currently in the subset)
        // and memo[i] is exactly 1 less than memo[prevIdx], meaning memo[prevIdx] was incremented because of nums[i]
        vector<int> maxDivisibleSubset;
        maxDivisibleSubset.push_back(nums[largestElementIdx]);
        int prevIdx = largestElementIdx;
        for (int i = largestElementIdx - 1; i >= 0; i--) {
        	if (maxDivisibleSubset.back() % nums[i] == 0 && memo[i] == memo[prevIdx] - 1) {
        		maxDivisibleSubset.push_back(nums[i]);
        		prevIdx = i;
        	}
        }
        return maxDivisibleSubset;
    }
    

Log in to reply
 

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