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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
|
import java.util.ArrayList; import java.util.Arrays; import java.util.List;
public class {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length; int dp[] = new int[n]; int ptr[] = new int[n];
for (int i=0; i<ptr.length; i++){ ptr[i] = -1; }
List<Integer> res = new ArrayList<>();
int idx=0; Arrays.sort(nums);
for (int i=1; i<nums.length; i++){ for (int j=0; j<i; j++){ if (nums[i] % nums[j]==0){ dp[i] = dp[j] + 1; ptr[i] = j; if (dp[i] > dp[idx]){ idx = i; } } } }
while(idx != -1){ res.add(nums[idx]); idx = ptr[idx]; } return res; } }
|
近期评论