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 那样看到大的就停手，要走到底 e.g. [1,2,4,7,28]

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

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> ans = new ArrayList<Integer>();
        if(nums==null || nums.length==0) return ans;
        int n = nums.length;
        int[] dp = new int[n]; Arrays.fill(dp, 1);
        int[] path = new int [n]; Arrays.fill(path, -1);

        Arrays.sort(nums);

        int maxidx = 0;
        for(int i=0;i<n;i++){
            dp[i] = 1;
            for(int j=i-1;j>=0;j--){
                if(nums[i]%nums[j]==0){
                    if(dp[i]<dp[j]+1){

                        dp[i] = dp[j]+1;
                        path[i] = j;
                        System.out.println(i+" " + dp[i]);
                    }
                }
            }
            if(dp[i]>dp[maxidx]) maxidx = i;
        }

        while(maxidx!=-1){
            System.out.println(maxidx);
            ans.add(0, nums[maxidx]);
            maxidx = path[maxidx];
        }
        return ans;
    }
}

暴力递归 TLE

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

        Arrays.sort(nums);

        int[] max = new int[1];
        List<Integer> result = new ArrayList<Integer>();
        helper(nums, 0, result, max);
        return answer;
    }

    public void helper(int[] nums, int start, List<Integer> result, int[] max){
        if(result.size()>max[0]){
            max[0]=result.size();
            answer=new ArrayList<Integer>(result);
        }

        if(start==nums.length)
            return;

        for(int i=start; i<nums.length; i++){
            if(result.size()==0){
                result.add(nums[i]);
                helper(nums, i+1, result, max);
                result.remove(result.size()-1);

            }else{

                int top = result.get(result.size()-1);
                if(nums[i]%top==0){
                    result.add(nums[i]);
                    helper(nums, i+1, result, max);
                    result.remove(result.size()-1);
                }
            }
        }
    }
}