Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:
answer[i] % answer[j] == 0, oranswer[j] % answer[i] == 0
If there are multiple solutions, return any of them.
Example 1:
Input: nums = [1,2,3] Output: [1,2] Explanation: [1,3] is also accepted.
Example 2:
Input: nums = [1,2,4,8] Output: [1,2,4,8]
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 2 * 109- All the integers in
numsare unique.
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
nums.sort()
n = len(nums)
f, p = [0] * n, [0] * n
for i in range(n):
l, pre = 1, i
for j in range(n):
if nums[i] % nums[j] == 0 and f[j] + 1 > l:
l = f[j] + 1
pre = j
f[i] = l
p[i] = pre
max_len, max_index = 0, 0
for i, v in enumerate(f):
if max_len < v:
max_len = v
max_index = i
ans = []
while len(ans) < max_len:
ans.append(nums[max_index])
max_index = p[max_index]
return ans[::-1]class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int[] f = new int[n], p = new int[n];
for (int i = 0; i < n; i++) {
int l = 1, pre = i;
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && f[j] + 1 > l) {
l = f[j] + 1;
pre = j;
}
}
f[i] = l;
p[i] = pre;
}
int maxLen = 0, maxIndex = 0;
for (int i = 0; i < n; i++) {
if (f[i] > maxLen) {
maxLen = f[i];
maxIndex = i;
}
}
List<Integer> ans = new ArrayList<>();
while (ans.size() < maxLen) {
ans.add(nums[maxIndex]);
maxIndex = p[maxIndex];
}
Collections.reverse(ans);
return ans;
}
}