最大整除子集

368. 最大整除子集

难度中等207收藏分享切换为英文接收动态反馈

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

如果有多个目标子集，返回其中任何一个均可。

示例 1:

输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)

示例 2:

输入: [1,2,4,8]
输出: [1,2,4,8]

动态规划

class Solution {
  public List<Integer> largestDivisibleSubset(int[] nums) {
    // Test case with empty set.
    int n = nums.length;
    if (n == 0) return new ArrayList();
        
    // Container to keep the largest divisible subset
    //   that ends with each of the nums.
    List<ArrayList> EDS = new ArrayList();
    for (int num : nums) EDS.add(new ArrayList());

    /* Sort the original list in ascending order. */
    Arrays.sort(nums);

    /* Calculate all the values of EDS(X_i) */
    for (int i = 0; i < n; ++i) {
      List<Integer> maxSubset = new ArrayList();
            
      // Find the largest divisible subset of previous elements.
      for (int k = 0; k < i; ++k) 
        if (nums[i] % nums[k] == 0 && maxSubset.size() < EDS.get(k).size())
          maxSubset = EDS.get(k);
          
      // Extend the found subset with the element itself.
      EDS.get(i).addAll(maxSubset);
      EDS.get(i).add(nums[i]);
    }
    /* Find the largest of EDS values  */
    List<Integer> ret = new ArrayList();
    for (int i = 0; i < n; ++i) 
      if (ret.size() < EDS.get(i).size()) ret = EDS.get(i);
    return ret;
  }  
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/largest-divisible-subset/solution/zui-da-zheng-chu-zi-ji-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

优化的动态规划

class Solution {
  public List<Integer> largestDivisibleSubset(int[] nums) {
    // Test case with empty set.
    int n = nums.length;
    if (n == 0) return new ArrayList();
        
    // Container to keep the size of the largest divisible subset
    //   that ends with each of the nums.
    Integer[] dp = new Integer[n];

    /* Sort the original list in ascending order. */
    Arrays.sort(nums);

    Integer maxSubsetSize = -1, maxSubsetIndex = -1;
    
    /* Calculate the rest of EDS(X_i) */
    for (int i = 0; i < n; ++i) {
      Integer subsetSize = 0;

      // Find the size of the largest divisible subset.
      for (int k = 0; k < i; ++k) 
        if (nums[i] % nums[k] == 0 && subsetSize < dp[k])
          subsetSize = dp[k];

      // Extend the found subset with the element itself.
      dp[i] = subsetSize + 1;
    
      // We reuse this loop to obtain the largest subset size 
      //   in order to prepare for the reconstruction of subset.
      if (maxSubsetSize < dp[i]) {
        maxSubsetSize = dp[i];
        maxSubsetIndex = i;
      }
    }
    
    /* Reconstruct the largest divisible subset  */
    LinkedList<Integer> subset = new LinkedList();
    Integer currSize = maxSubsetSize;
    Integer currTail = nums[maxSubsetIndex];
    for (int i = maxSubsetIndex; i >= 0; --i) {
      if (currSize == 0) break;
    
      if (currTail % nums[i] == 0 && currSize == dp[i]) {
        subset.addFirst(nums[i]);
        currTail = nums[i];
        currSize -= 1;
      }
    }

    return subset;
  }  
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/largest-divisible-subset/solution/zui-da-zheng-chu-zi-ji-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信