Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/368.html

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, or
  • answer[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 <= 1000
  • 1 <= nums[i] <= 2 * 109
  • All the integers in nums are unique.

Algorithm

The remainder of the smaller number to the larger number must not be 0, then the question becomes whether the larger number can divide the smaller number evenly.

So if the array is unordered, it will be more troublesome to process, so we can sort the array first, so that we only need to see whether the following numbers can divide the previous numbers every time.

Define a dynamic array dp, where dp[i] represents the length of the largest divisible subset of the number nums[i] position.

A one-dimensional array parent is also needed to store the position of the last divisible number. The two integer variables mx and mx_idx respectively represent the length of the largest subset and the position of the starting number.

We can traverse the array from back to front, and then traverse to the end for a certain number. In this process

  • If nums[j] can divide nums[i] evenly, and dp[i] <dp[j] + 1, update dp[i] and parent[i]
  • If dp[i] is greater than mx, update mx and mx_idx

After the end of the loop, we fill in the res number and find each number according to the parent array.

Code

  • import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Largest_Divisible_Subset {
    
        public static void main(String[] args) {
            Largest_Divisible_Subset out = new Largest_Divisible_Subset();
            Solution s = out.new Solution();
    
            System.out.println(s.largestDivisibleSubset(new int[]{1,2,3,4,7,8}));
        }
    
    
        class Solution {
    
            public List<Integer> largestDivisibleSubset(int[] nums) {
    
                Arrays.sort(nums);
                List<Integer> res = new ArrayList<>();
    
                // dp[i] represents the length of the largest divisible subset of the number nums[i] position
                int[] dp = new int[nums.length];
    
                int[] parent = new int[nums.length];
    
                int maxLength = 0, maxIndex = 0;
    
                // i is from back to front, so that when out of loop, maxIndex is at the smallest index to trace back
                for (int i = nums.length - 1; i >= 0; 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, also working but repeated write
                            dp[i] = dp[j] + 1;
                            parent[i] = j;
                            if (maxLength < dp[i]) {
                                maxLength = dp[i];
                                maxIndex = i;
                            }
                        }
                    }
                }
    
                for (int i = 0; i < maxLength; ++i) {
                    // back-tracking
                    res.add(nums[maxIndex]);
                    maxIndex = parent[maxIndex];
                }
    
                return res;
            }
        }
    }
    
    ############
    
    class Solution {
        public List<Integer> largestDivisibleSubset(int[] nums) {
            Arrays.sort(nums);
            int n = nums.length;
            int[] f = new int[n];
            Arrays.fill(f, 1);
            int k = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < i; ++j) {
                    if (nums[i] % nums[j] == 0) {
                        f[i] = Math.max(f[i], f[j] + 1);
                    }
                }
                if (f[k] < f[i]) {
                    k = i;
                }
            }
            int m = f[k];
            List<Integer> ans = new ArrayList<>();
            for (int i = k; m > 0; --i) {
                if (nums[k] % nums[i] == 0 && f[i] == m) {
                    ans.add(nums[i]);
                    k = i;
                    --m;
                }
            }
            return ans;
        }
    }
    
  • // OJ: https://leetcode.com/problems/largest-divisible-subset/
    // Time: O(N^2)
    // Space: O(N)
    class Solution {
    public:
        vector<int> largestDivisibleSubset(vector<int>& A) {
            sort(begin(A), end(A));
            int N = A.size(), last = 0;
            vector<int> dp(N, 1), prev(N, -1), ans;
            for (int i = 1; i < N; ++i) {
                for (int j = 0; j < i; ++j) {
                    if (A[i] % A[j] == 0 && dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        prev[i] = j;
                    }
                }
                if (dp[i] > dp[last]) last = i;
            }
            for (int i = last; i != -1; i = prev[i]) ans.push_back(A[i]);
            return ans;
        }
    };
    
  • class Solution:
        def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
            nums.sort()
            n = len(nums)
            dp = [0] * n
            parent = [0] * n
            max_index, max_length = 0, 0
    
            for i in range(n - 1, -1, -1):
                for j in range(i, n): # note: not i+1
                    if nums[j] % nums[i] == 0 and dp[i] < 1 + dp[j]:
                        dp[i] = 1 + dp[j]
                        parent[i] = j
    
                        if dp[i] > max_length:
                            max_length = dp[i]
                            max_index = i
            res = []
            for _ in range(max_length):
                res.append(nums[max_index])
                max_index = parent[max_index]
    
            return res
    
    ############
    
    class Solution(object):
      def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums) < 2:
          return nums
        ans = []
        nums.sort()
        dp = [1] * len(nums)
        path = [-1] * len(nums)
        finalMaxLen, finalMaxLenIdx = -1, -1
        for i in range(1, len(nums)):
          maxLen, maxLenIdx = -1, -1
          for j in range(0, i):
            if nums[i] % nums[j] == 0:
              if dp[j] >= maxLen:
                maxLen = dp[j]
                maxLenIdx = j
          dp[i] = maxLen + 1
          path[i] = maxLenIdx
          if dp[i] >= finalMaxLen:
            finalMaxLen = dp[i]
            finalMaxLenIdx = i
    
        while finalMaxLenIdx != -1:
          ans.append(nums[finalMaxLenIdx])
          finalMaxLenIdx = path[finalMaxLenIdx]
        return ans
    
    
  • func largestDivisibleSubset(nums []int) (ans []int) {
    	sort.Ints(nums)
    	n := len(nums)
    	f := make([]int, n)
    	k := 0
    	for i := 0; i < n; i++ {
    		f[i] = 1
    		for j := 0; j < i; j++ {
    			if nums[i]%nums[j] == 0 {
    				f[i] = max(f[i], f[j]+1)
    			}
    		}
    		if f[k] < f[i] {
    			k = i
    		}
    	}
    	m := f[k]
    	for i := k; m > 0; i-- {
    		if nums[k]%nums[i] == 0 && f[i] == m {
    			ans = append(ans, nums[i])
    			k = i
    			m--
    		}
    	}
    	return
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions