leetCode-368:Largest Divisible Subset

问题描述

给定一个只包含正整数的不存在重复元素的数组，要求找出包含最大长度的子集合（存在多个时返回任意一个即可），该子集合中的元素满足任意两个元素都能整除。题目链接：点我

样例输入输出

输入：nums = [1,2,3]

输出：[1, 2] 或 [1, 3]

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

输出：[1, 2, 4, 8]

问题解法

此题就是查找数组中的最大互为公约数子序列。可以使用动态规划求解，先对数组进行排序，然后用 dp[i] 表示以 i 位置元素为递增乘数队列的最后一个元素，则可遍历 [0, i - 1] 中的元素，如果当中某个元素时 i 元素的公约数，则可表示将 i 元素加入到 k 元素的列表中。动态转移方程为 dp[i] = max(dp[k]) + 1，最后，取 dp 数组中元素最大值就是目标数组的元素个数。以此为结果可以倒推结果数组中的每个元素。代码如下

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int[] dpIndex = new int[nums.length];
        int[] dpCount = new int[nums.length];
        Arrays.fill(dpIndex, -1);
        Arrays.fill(dpCount, 1);

        int maxCount = -1;
        int lastIndex = 0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (dpCount[j] + 1 > dpCount[i]) {
                        dpCount[i] = dpCount[j] + 1;
                        dpIndex[i] = j;
                    }
                }
            }

            if (dpCount[i] > maxCount) {
                maxCount = dpCount[i];
                lastIndex = i;
            }
        }

        List<Integer> result = new ArrayList<>();
        while (lastIndex != -1) {
            result.add(nums[lastIndex]);
            lastIndex = dpIndex[lastIndex];
        }

        return result;
    }
}