368. Largest Divisible Subset - cocoder39/coco39_LC GitHub Wiki

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        n = len(nums)
        if n == 0:
            return []
        
        nums.sort()
        dp = [1] * n
        
        max_length = 0
        idx = -1
        for i in range(n):
            for j in range(i-1, -1, -1):
                if nums[i] % nums[j] == 0:
                    dp[i] = max(dp[i], dp[j] + 1)
                    if dp[i] > max_length:
                        max_length = dp[i]
                        idx = i
        
        res = [nums[idx]]
        length = max_length - 1
        for i in range(idx-1, -1, -1):
            if length == 0:
                break
            if res[-1] % nums[i] == 0 and dp[i] == length:
                res.append(nums[i])
                length -= 1
        return res

vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int sz = nums.size();
        vector<int> dp(sz); //dp[i] is longest path of subset whose max element is nums[i]
        vector<int> parent(sz, -1); //back track the longest path
        int len = 0; //length of longest path
        int last = -1; //nums[last] is max element in longest subset
        
        for (int i = 0; i < sz; i++) { //O(n ^ 2)
            dp[i] = 1; //single element
            for (int 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 (len < dp[i]) {
                len = dp[i];
                last = i;
            }
        }
        
        vector<int> res(len);
        for (int i = len; i > 0; i--) {
            res[i - 1] = nums[last];
            last = parent[last];
        }
        return res;
    }