Array, Dynamic Programming, Sorting O(n^2)
IntuitionThe problem is a variation of the Longest Increasing Subsequence (LIS), but instead of looking for increasing numbers, we're looking for a sequence whe
# Intuition
The problem is a variation of the Longest Increasing Subsequence (LIS), but instead of looking for increasing numbers, we're looking for a sequence where each element is divisible by its predecessor. To maximize the size of the subset, it's helpful to sort the array first, allowing us to build divisible chains in a left-to-right manner.

# Approach
1. **Sort the input**: Sorting ensures that if `a % b == 0`, then `a >= b`. This allows us to try building subsets from smaller to larger elements.
2. **Dynamic Programming**:  
   - We use a `dp` list where each entry `dp[i]` contains the largest divisible subset ending with `nums[i]`.
   - For every `nums[i]`, we check all previous `nums[j]` where `j < i`. If `nums[i] % nums[j] == 0` and the subset ending at `j` is longer than the one at `i`, we update `dp[i]` as `dp[j] + [nums[i]]`.
3. **Return the longest subset**: After filling the `dp` list, the longest subset is the one with the maximum length.

This approach ensures we build the longest divisible subset dynamically by chaining compatible numbers.

# Complexity
- Time complexity:  
  $$O(n^2)$$  
  We have nested loops where for each `i`, we check all `j < i`.

- Space complexity:  
  $$O(n^2)$$  
  In the worst case, each `dp[i]` stores a list of size up to `n`.

# Code
```python3 []
class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        dp = [[num] for num in nums]

        for i in range(len(nums)):
            for j in range(i):
                if nums[i] % nums[j] == 0 and len(dp[j]) + 1 > len(dp[i]):
                    dp[i] = dp[j] + [nums[i]]

        return max(dp, key=len)
```
['Array', 'Dynamic Programming', 'Sorting', 'Python3']