动态规划

2021-4-23

368. 最大整除子集

题目链接
难度：中等
给你一个由无重复正整数组成的集合nums，请你找出并返回其中最大的整除子集answer，子集中每一元素对(answer[i], answer[j])都应当满足：

  • answer[i] % answer[j] == 0，或
  • answer[j] % answer[i] == 0

如果存在多个有效解子集，返回其中任何一个均可。
示例 1：
输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。

示例 2：
输入：nums = [1,2,4,8]
输出：[1,2,4,8]

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 2 * 109
  • nums中的所有整数互不相同
    1. class Solution {
    2.   public List<Integer> largestDivisibleSubset(int[] nums) {
    3.       int len = nums.length;
    4.       List<Integer> ans = new ArrayList<Integer>();
    5.       if (len == 1){
    6.           ans.add(nums[0]);
    7.           return ans;
    8.       }
    9.       int max = -1;// 记录最大值
    10.       int index = 0;// 记录最大值的位置
    11.       int[] dp = new int[len];// 动规数组
    12.       Arrays.sort(nums);// 先排序，方便取模
    13.       dp[0] = 1;// 默认自身可以对自身取模即设置为1
    14.       for (int i=1;i<len;i++) {
    15.           dp[i] = 1;
    16.           for (int j=0;j<i;j++) {//从0到当前位置进行取模比较
    17.               if (nums[i] % nums[j] == 0) {
    18.                   dp[i] = Math.max(dp[j] + 1,dp[i]); // 取最大值
    19.               }
    20.           }
    21.           // 记录最大值
    22.           if (dp[i] > max) {
    23.               max = dp[i];
    24.               index = i;
    25.           }
    26.       }
    27.       // 如果没有取得最大值，默认为0；
    28.       if (max == -1) {
    29.           ans.add(nums[0]);
    30.           return ans;
    31.       }
    32.       // for (int i=0;i<len;i++){
    33.       //     System.out.print(dp[i]+" ");
    34.       // }
    35.       // System.out.print("**"+max+" "+index+" "+dp[index]);
    36.       int cnt = max;// 最大值计数器，用于回溯
    37.       for(int i = index;i>=0;i--) {
    38.           if (nums[index] % nums[i] == 0 && dp[i] == cnt) {// 如果可以取模并且数值相等
    39.               ans.add(nums[i]);
    40.               index = i;
    41.               cnt--;
    42.           }
    43.       }
    44.       Collections.reverse(ans);// 翻转数组
    45.       return ans;
    46.   }
    47. }