368 Largest Divisible Subset

368. Largest Divisible Subset​
1. 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:
1
nums: [1,2,3]
2
​
3
Result: [1,2] (of course, [1,3] will also be ok)
Copied!
Example 2:
1
nums: [1,2,4,8]
2
​
3
Result: [1,2,4,8]
Copied!
2. Implementation
思路: 因为要找的是最大的subset，我们发现最后我们要找的结果和它当前的位置是无关的，所以为了方便比较，我们先对输入的数组排序。然后我们用类似于找Longest Increasing Subsequence的方式找到最大的divisible subset。我们用count和preIndex两个数组分别记录以下信息: count[i]表示在位置i之前的，最大的divisible subset的size，preIndex[i]记录i之前的上一个divisible subset的元素。比如如果 nums[i] % nums[j] == 0 and j < i, preIndex[i] = j. 最后有一点要注意的是，如果subset只有1个元素，那么很明显这是个合法的解(自己余自己等于0)，所以第一个for loop里我们先从i = 0开始，而不是i = 1
(1) DP
1
class Solution {
2
    public List<Integer> largestDivisibleSubset(int[] nums) {
3
        List<Integer> res = new ArrayList<>();
4
​
5
        if (nums == null || nums.length == 0) {
6
            return res;
7
        }
8
​
9
        Arrays.sort(nums);
10
        int n = nums.length;
11
        int[] count = new int[n];
12
        int[] preIndex = new int[n];
13
        int max = 0, index = -1;
14
​
15
​
16
        for (int i = 0; i < n; i++) {
17
            count[i] = 1;
18
            preIndex[i] = -1;
19
            for (int j = i - 1; j >= 0; j--) {
20
                if (nums[i] % nums[j] == 0 && (1 + count[j] > count[i])) {
21
                    count[i] = count[j] + 1;
22
                    preIndex[i] = j;
23
                }
24
            }
25
             if (count[i] > max) {
26
                max = count[i];
27
                index = i;
28
            }
29
        }
30
​
31
        while (index != -1) {
32
            res.add(nums[index]);
33
            index = preIndex[index];
34
        }
35
        return res;
36
    }
37
}
Copied!
3. Time & Space Complexity
DP: 时间复杂度O(n^2), 空间复杂度O(n)

363 Max Sum of Rectangle No Larger Than K

403 Frog Jump

Last modified 2yr ago

Copy link

Contents

368. Largest Divisible Subset

1. Question

2. Implementation

3. Time & Space Complexity

368. Largest Divisible Subset​

1. Question

2. Implementation

3. Time & Space Complexity

368. Largest Divisible Subset