Largest Divisible Subset

medium array dp sorting

Problem

Given a set of distinct positive integers, return the largest subset such that for every pair (a, b) either a % b == 0 or b % a == 0.

Inputnums = [1, 2, 4, 8]

Output[1, 2, 4, 8]

Sort, then dp[i] = longest divisible chain ending at i. Recover with a parent pointer.

nums

def largest_divisible_subset(nums):
    nums.sort()
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    best_i = 0
    for i in range(n):
        for j in range(i):
            if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
        if dp[i] > dp[best_i]:
            best_i = i
    out = []
    while best_i != -1:
        out.append(nums[best_i])
        best_i = prev[best_i]
    return out[::-1]

function largestDivisibleSubset(nums) {
  nums.sort((a, b) => a - b);
  const n = nums.length;
  const dp = new Array(n).fill(1), prev = new Array(n).fill(-1);
  let bestI = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] % nums[j] === 0 && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1; prev[i] = j;
      }
    }
    if (dp[i] > dp[bestI]) bestI = i;
  }
  const out = [];
  while (bestI !== -1) { out.push(nums[bestI]); bestI = prev[bestI]; }
  return out.reverse();
}

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n], prev = new int[n];
        Arrays.fill(dp, 1); Arrays.fill(prev, -1);
        int bestI = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1; prev[i] = j;
                }
            }
            if (dp[i] > dp[bestI]) bestI = i;
        }
        LinkedList<Integer> out = new LinkedList<>();
        while (bestI != -1) { out.addFirst(nums[bestI]); bestI = prev[bestI]; }
        return out;
    }
}

vector<int> largestDivisibleSubset(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<int> dp(n, 1), prev(n, -1);
    int bestI = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; prev[i] = j; }
        if (dp[i] > dp[bestI]) bestI = i;
    }
    vector<int> out;
    while (bestI != -1) { out.push_back(nums[bestI]); bestI = prev[bestI]; }
    reverse(out.begin(), out.end());
    return out;
}

Explanation

We need the largest group of numbers where, for any two, one divides the other. The clever observation: if we sort the numbers first, then in any valid group each number only has to divide the next one — divisibility chains forward automatically.

After sorting, this becomes a longest-chain problem just like Longest Increasing Subsequence. We set dp[i] = the length of the best divisible chain ending at index i, starting everyone at 1.

For each i we look back at every earlier j. If nums[i] % nums[j] == 0 and extending j's chain is longer, we set dp[i] = dp[j] + 1 and record prev[i] = j so we can rebuild the chain later.

We track the index with the largest dp value, then walk the prev pointers backward and reverse to get the actual subset.

Example: [1, 2, 4, 8] is already sorted and each divides the next, so the whole array forms the chain and is returned.

Time: O(n²) Space: O(n)