Question

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.

Example 1:
nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)

Example 2:
nums: [1,2,4,8]
Result: [1,2,4,8]

Code

public class Solution {
    public class Data {
        public int index;
        public int count;
        public int pre;
        
        public Data(int index, int count, int pre) {
            this.index = index;
            this.count = count;
            this.pre = pre;
        }
    }
    
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        if (nums.length == 1) {
            result.add(nums[0]);
            return result;
        }
        
        Arrays.sort(nums);
        
        Data[] dp = new Data[nums.length];
        dp[0] = new Data(0, 1, 0);
        int max = 1;
        Data record = dp[0];
        
        for (int i = 1; i < dp.length; i++) {
            dp[i] = new Data(i, 1, i);
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (dp[j].count + 1 > dp[i].count) {
                        dp[i].count = dp[j].count + 1;
                        dp[i].pre = j;
                    }
                    if (dp[i].count > max) {
                            max = dp[i].count;
                            record = dp[i];
                    }
                }
            }
        }
        
        while (record.index != record.pre) {
            result.add(0, nums[record.index]);
            record = dp[record.pre];
        }
        result.add(0, nums[record.index]);
        return result;
    }
}

Solution

動態(tài)規(guī)劃實現(xiàn)。

實現(xiàn)了一個內(nèi)部類，類中包含三個元素：index表示該元素在nums中的下標(biāo)，count表示含有nums[index]的最大可除子序列的長度，pre表示該序列的前一個元素在nums中的下標(biāo)。初始化時，pre = index， count = 1.

對于nums中的每一個元素nums[i]，遍歷其之前的nums[j]，當(dāng)nums[i] % nums[j] == 0時，使用狀態(tài)轉(zhuǎn)移方程：dp[i].count = Math.max(dp[i].count, dp[j].count + 1)。同時更新dp[i].pre = j。在遍歷nums[i]的過程中，用int max記錄最大的count，用Data record記錄擁有最大count的Data。

遍歷完成后，通過record.pre不斷回溯，將所有的num添加到結(jié)果集中。