Largest Divisible Subset

• Lintcode : 603 / Leetcode : 368
• Level : Medium

Problem

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

Example
Example 1:

Input: nums =  [1,2,3], 
Output: [1,2] or [1,3]
Example 2:

Input: nums = [1,2,4,8], 
Output: [1,2,4,8]
Notice
If there are multiple solutions, return any subset is fine.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n ^ 2)
space: O(n ^ 2)

Answer

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int> &nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> dp(n);
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            int maxLength = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] % nums[j] == 0) {
                    int len = dp[j].size();
                    if (len > maxLength) {
                        dp[i] = dp[j];
                        maxLength = len;
                    }
                }
            }
            dp[i].push_back(nums[i]);
            int dpSize = dp[i].size();
            if (dpSize > ans.size()) {
                ans = dp[i];
            }
        }
        return ans;
    }
};

tags: DP

​