# 368. 最大整除子集(368. Maximum divisible subset)-其他

## 368. 最大整除子集(368. Maximum divisible subset)

``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
if (nums == null || nums.length == 0) {
return Collections.emptyList();
}
Arrays.sort(nums);
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int max = 1, maxIndex = 0;
for (int i = 0; i < nums.length; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] % nums[j] == 0) {
dp[i] = Math.max(dp[i], dp[j] + 1);
if (dp[i] > max) {
max = dp[i];
maxIndex = i;
}
}
}
}
List<Integer> ans = new ArrayList<>();

for (int i = maxIndex; i >= 0; --i) {
if (nums[maxIndex] % nums[i] == 0 && dp[i] == max - ans.size()) {
maxIndex = i;
}
}
Collections.reverse(ans);
return ans;
}
}
``````
————————

Give you a set num composed of non repeating positive integers. Please find and return the largest integer division subset answer. Each element pair (answer [i], answer [J]) in the subset should meet:
If there are multiple valid solution subsets, any of them can be returned.

Source: leetcode

``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
if (nums == null || nums.length == 0) {
return Collections.emptyList();
}
Arrays.sort(nums);
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int max = 1, maxIndex = 0;
for (int i = 0; i < nums.length; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] % nums[j] == 0) {
dp[i] = Math.max(dp[i], dp[j] + 1);
if (dp[i] > max) {
max = dp[i];
maxIndex = i;
}
}
}
}
List<Integer> ans = new ArrayList<>();

for (int i = maxIndex; i >= 0; --i) {
if (nums[maxIndex] % nums[i] == 0 && dp[i] == max - ans.size()) {