#368. Largest Divisible Subset

https://leetcode.com/problems/largest-divisible-subset/description/?envType=daily-question&envId=2024-02-09

function largestDivisibleSubset(nums) {
    if (nums.length === 0) return [];

    nums.sort((a, b) => a - b);

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

    let maxSubsetLength = 1;
    let maxSubsetEndIndex = 0;

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] % nums[j] === 0 && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        if (dp[i] > maxSubsetLength) {
            maxSubsetLength = dp[i];
            maxSubsetEndIndex = i;
        }
    }

    const maxSubset = [];
    while (maxSubsetEndIndex !== -1) {
        maxSubset.push(nums[maxSubsetEndIndex]);
        maxSubsetEndIndex = parent[maxSubsetEndIndex];
    }

    return maxSubset.reverse();
}

Another dynamic problem solved with chatGPT