🌕 368. 最大整除子集

难度: 🌕

问题描述

---

解法

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        // 思路：
        // dp - 首先找到最大整除子集的长度
        // 根据最长子集的长度依次往前找前面的元素

        Arrays.sort(nums); // 先排序
        int len = nums.length;
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        int count = 1;
        int val = nums[0];
        int index = 0;
        // dp
        for(int i = 1; i < len; i ++) {
            int cur = nums[i]; // 找以 cur 为最后元素的整除子集
            for(int j = 0; j < i; j ++) {
                if(cur % nums[j] == 0) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 判断是否更新最大子集长度
            if(dp[i] > count) {
                count = dp[i];
                val = cur;
                index = i;
            }
        }
        // 确定 dp[i] 后，填充 res
        ArrayList<Integer> res = new ArrayList<>();
        // 先将最后一个元素加入结果集中
        res.add(val);
        count --;
        // 从后往前找
        for(int i = index - 1; i >= 0; i --) {
            if(dp[i] == count && val % nums[i] == 0) {
                count --;
                res.add(nums[i]);
                val = nums[i];
            }
        }
        return res;
    }
}

---

输出