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

動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)。

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

對(duì)于nums中的每一個(gè)元素nums[i]，遍歷其之前的nums[j]账磺，當(dāng)nums[i] % nums[j] == 0時(shí)芹敌，使用狀態(tài)轉(zhuǎn)移方程：dp[i].count = Math.max(dp[i].count, dp[j].count + 1)。同時(shí)更新dp[i].pre = j垮抗。在遍歷nums[i]的過(guò)程中氏捞，用int max記錄最大的count，用Data record記錄擁有最大count的Data冒版。

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