Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public List<Integer> largestDivisibleSubset(int[] nums) {
- Arrays.sort(nums);
- int maxSubsetLength = 0;
- int maxSubsetLengthStartIndex = 0;
- int[] dp = new int[nums.length];
- int[] parent = new int[nums.length]; // to keep track of the subset forming a chain
- // Useful concept for other problems as well.
- for(int i = nums.length - 1 ; i >= 0; i--) {
- parent[i] = i;
- for(int j = i; j < nums.length; j++) {
- if(nums[j] % nums[i] == 0 && dp[i] < dp[j] + 1) {
- dp[i] = dp[j] + 1;
- parent[i] = j;
- if(dp[i] > maxSubsetLength) {
- maxSubsetLength = dp[i];
- maxSubsetLengthStartIndex = i;
- }
- }
- }
- }
- List<Integer> result = new ArrayList<>();
- while(maxSubsetLengthStartIndex < nums.length) {
- result.add(nums[maxSubsetLengthStartIndex]);
- if(maxSubsetLengthStartIndex == parent[maxSubsetLengthStartIndex]) break;
- maxSubsetLengthStartIndex = parent[maxSubsetLengthStartIndex];
- }
- return result;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement