Largest Divisible Subset

这个博客的文章讲的不错~ 重点比我说的好。https://segmentfault.com/a/1190000005922634

Largest Divisible Subset

把这题放在 LIS 分类下面，主要是因为长的和 LIS 的 O(n^2) DP 解法很像。

这题正确性的保证：对于排序数组 nums 的两个 index，i, j 并且 j < i 的情况下，如果 nums[i] % nums[j] == 0，那么包含 nums[j] 的 subset 里所有元素也一定能整除 nums[i]. 因为 nums[j] 是其 subset 中当前最大的元素，而且一定可以整除所有比它小的。

主要不同点：

• 因为最后要输出结果，得存个 parent 数组记录每个序列的前一个元素

• 每次往回扫的时候，不能像 LIS 那样看到大的就停手，要走到底

这么讲的话，貌似要输出具体 LIS 序列的题，也可以这么做。。O(n^2) 时间，O(n) 空间就可以了。

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> rst = new ArrayList<>();
        if(nums == null || nums.length == 0) return rst;

        Arrays.sort(nums);
        int[] dp = new int[nums.length];
        int[] parent = new int[nums.length];
        Arrays.fill(dp, 1);
        Arrays.fill(parent, -1);

        int maxIndex = -1;
        int maxLen = 1;

        for(int i = 0; i < nums.length; i++){
            for(int j = i - 1; j >= 0; j--){
                if(nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                    parent[i] = j;

                    if(dp[i] > maxLen){
                        maxLen = dp[i];
                        maxIndex = i;
                    }
                }
            }
        }

        if(maxIndex == -1){
            rst.add(nums[0]);
        } else {
            while(maxIndex != -1){
                rst.add(nums[maxIndex]);
                maxIndex = parent[maxIndex];
            }
        }

        return rst;
    }
}