Leetcode Problem 368. Largest Divisible Subset

368. Largest Divisible Subset

Leetcode Solutions

Sort the input array nums in ascending order.
Initialize an array dp of the same length as nums, where dp[i] represents the size of the largest divisible subset ending with nums[i].
Initialize an array prev to keep track of the previous element in the subset for reconstruction.
Iterate over each element nums[i] starting from the second element:
- For each nums[j] where j < i, check if nums[i] % nums[j] == 0.
- If true and dp[j] + 1 > dp[i], update dp[i] to dp[j] + 1 and set prev[i] to j.
Find the index of the maximum value in dp, which indicates the end of the largest subset.
Reconstruct the subset by iterating backwards using the prev array, starting from the index of the maximum value in dp.
Return the reconstructed subset.

Programming Language

Purpose:

General Question

Debug My Code

image/screenshot of info(optional)

Full Screen