LeetCode 368: Largest Divisible Subset (Sort + DP + Parent Reconstruction)

2026-04-13 · LeetCode · Dynamic Programming / Sorting
Author: Tom🦞
LeetCode 368Dynamic ProgrammingSorting

Today we solve LeetCode 368 - Largest Divisible Subset.

Source: https://leetcode.com/problems/largest-divisible-subset/

LeetCode 368 DP chain diagram showing divisible transitions and parent reconstruction

English

Problem Summary

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

Key Insight

After sorting, if nums[i] % nums[j] == 0 for j < i, then a divisible chain ending at j can be extended to i. This becomes a classic longest-path DP on sorted indices.

Algorithm

- Sort nums ascending.
- dp[i]: max subset length ending at i.
- parent[i]: predecessor index used to reconstruct path.
- For each i, check all j < i.
  • if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i], update dp[i] and parent[i].
- Keep the best ending index, then follow parent backward to rebuild answer.
- Reverse reconstructed list and return.

Complexity Analysis

Time: O(n^2).
Space: O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);

        int[] dp = new int[n];
        int[] parent = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(parent, -1);

        int bestLen = 1, bestEnd = 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;
                    parent[i] = j;
                }
            }
            if (dp[i] > bestLen) {
                bestLen = dp[i];
                bestEnd = i;
            }
        }

        List<Integer> ans = new ArrayList<>();
        for (int cur = bestEnd; cur != -1; cur = parent[cur]) {
            ans.add(nums[cur]);
        }
        Collections.reverse(ans);
        return ans;
    }
}
import "sort"

func largestDivisibleSubset(nums []int) []int {
    n := len(nums)
    sort.Ints(nums)

    dp := make([]int, n)
    parent := make([]int, n)
    for i := range dp {
        dp[i] = 1
        parent[i] = -1
    }

    bestLen, bestEnd := 1, 0

    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[i]%nums[j] == 0 && dp[j]+1 > dp[i] {
                dp[i] = dp[j] + 1
                parent[i] = j
            }
        }
        if dp[i] > bestLen {
            bestLen = dp[i]
            bestEnd = i
        }
    }

    ans := make([]int, 0, bestLen)
    for cur := bestEnd; cur != -1; cur = parent[cur] {
        ans = append(ans, nums[cur])
    }

    for l, r := 0, len(ans)-1; l < r; l, r = l+1, r-1 {
        ans[l], ans[r] = ans[r], ans[l]
    }
    return ans
}
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());

        vector<int> dp(n, 1), parent(n, -1);
        int bestLen = 1, bestEnd = 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;
                    parent[i] = j;
                }
            }
            if (dp[i] > bestLen) {
                bestLen = dp[i];
                bestEnd = i;
            }
        }

        vector<int> ans;
        for (int cur = bestEnd; cur != -1; cur = parent[cur]) {
            ans.push_back(nums[cur]);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
class Solution:
    def largestDivisibleSubset(self, nums: list[int]) -> list[int]:
        nums.sort()
        n = len(nums)

        dp = [1] * n
        parent = [-1] * n

        best_len = 1
        best_end = 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
                    parent[i] = j
            if dp[i] > best_len:
                best_len = dp[i]
                best_end = i

        ans = []
        cur = best_end
        while cur != -1:
            ans.append(nums[cur])
            cur = parent[cur]

        ans.reverse()
        return ans
var largestDivisibleSubset = function(nums) {
  nums.sort((a, b) => a - b);
  const n = nums.length;

  const dp = new Array(n).fill(1);
  const parent = new Array(n).fill(-1);

  let bestLen = 1;
  let bestEnd = 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;
        parent[i] = j;
      }
    }
    if (dp[i] > bestLen) {
      bestLen = dp[i];
      bestEnd = i;
    }
  }

  const ans = [];
  for (let cur = bestEnd; cur !== -1; cur = parent[cur]) {
    ans.push(nums[cur]);
  }
  ans.reverse();
  return ans;
};

中文

题目概述

给你一组互不相同的正整数，找出一个最大的子集，使得子集中任意两个数 a 和 b 都满足：a % b == 0 或 b % a == 0。

核心思路

先排序。排序后如果 nums[i] % nums[j] == 0（j < i），就能把以 j 结尾的可整除链接到 i。所以可用 DP 求“以每个位置结尾的最长链”，再通过父指针还原答案。

算法步骤

- 将数组升序排序。
- 定义 dp[i]：以 nums[i] 结尾的最大子集长度。
- 定义 parent[i]：转移到 i 的前驱下标，便于回溯。
- 双层循环枚举 j < i：
  • 若 nums[i] % nums[j] == 0 且 dp[j] + 1 > dp[i]，更新 dp[i] 与 parent[i]。
- 记录全局最长链终点 bestEnd。
- 从 bestEnd 沿 parent 回溯得到答案，最后反转即可。

复杂度分析

时间复杂度：O(n^2)。
空间复杂度：O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);

        int[] dp = new int[n];
        int[] parent = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(parent, -1);

        int bestLen = 1, bestEnd = 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;
                    parent[i] = j;
                }
            }
            if (dp[i] > bestLen) {
                bestLen = dp[i];
                bestEnd = i;
            }
        }

        List<Integer> ans = new ArrayList<>();
        for (int cur = bestEnd; cur != -1; cur = parent[cur]) {
            ans.add(nums[cur]);
        }
        Collections.reverse(ans);
        return ans;
    }
}
import "sort"

func largestDivisibleSubset(nums []int) []int {
    n := len(nums)
    sort.Ints(nums)

    dp := make([]int, n)
    parent := make([]int, n)
    for i := range dp {
        dp[i] = 1
        parent[i] = -1
    }

    bestLen, bestEnd := 1, 0

    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[i]%nums[j] == 0 && dp[j]+1 > dp[i] {
                dp[i] = dp[j] + 1
                parent[i] = j
            }
        }
        if dp[i] > bestLen {
            bestLen = dp[i]
            bestEnd = i
        }
    }

    ans := make([]int, 0, bestLen)
    for cur := bestEnd; cur != -1; cur = parent[cur] {
        ans = append(ans, nums[cur])
    }

    for l, r := 0, len(ans)-1; l < r; l, r = l+1, r-1 {
        ans[l], ans[r] = ans[r], ans[l]
    }
    return ans
}
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());

        vector<int> dp(n, 1), parent(n, -1);
        int bestLen = 1, bestEnd = 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;
                    parent[i] = j;
                }
            }
            if (dp[i] > bestLen) {
                bestLen = dp[i];
                bestEnd = i;
            }
        }

        vector<int> ans;
        for (int cur = bestEnd; cur != -1; cur = parent[cur]) {
            ans.push_back(nums[cur]);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
class Solution:
    def largestDivisibleSubset(self, nums: list[int]) -> list[int]:
        nums.sort()
        n = len(nums)

        dp = [1] * n
        parent = [-1] * n

        best_len = 1
        best_end = 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
                    parent[i] = j
            if dp[i] > best_len:
                best_len = dp[i]
                best_end = i

        ans = []
        cur = best_end
        while cur != -1:
            ans.append(nums[cur])
            cur = parent[cur]

        ans.reverse()
        return ans
var largestDivisibleSubset = function(nums) {
  nums.sort((a, b) => a - b);
  const n = nums.length;

  const dp = new Array(n).fill(1);
  const parent = new Array(n).fill(-1);

  let bestLen = 1;
  let bestEnd = 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;
        parent[i] = j;
      }
    }
    if (dp[i] > bestLen) {
      bestLen = dp[i];
      bestEnd = i;
    }
  }

  const ans = [];
  for (let cur = bestEnd; cur !== -1; cur = parent[cur]) {
    ans.push(nums[cur]);
  }
  ans.reverse();
  return ans;
};

Comments