Poison

368. Largest Divisible Subset

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums); // 不要忘记排序

        int n = nums.length;

        // 定义 dp[i] 为以 nums[i] 结尾的最大整除子集的长度
        int[] dp = new int[n];
        int[] prevMap = new int[n]; // curr -> prev

        int maxLength = 1;
        int endIndex = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1; // 单个元素满足条件
            int prevIndex = i;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prevIndex = j;
                }
            }
            prevMap[i] = prevIndex;

            if (dp[i] > maxLength) {
                maxLength = dp[i];
                endIndex = i;
            }
        }

        List<Integer> resultList = new ArrayList<>();
        for (int i = 0; i < maxLength; i++) {
            resultList.add(nums[endIndex]);
            endIndex = prevMap[endIndex];
        }
        return resultList;
    }
}
Reference

368. Largest Divisible Subset