Largest Divisible Subset

Leetcode Problem:

• Largest Divisible Subset

Summary

• Given a set of distinct positive integers, find the largest subset such that every pair of elements in the subset satisfies either element is divisible by the other.

Approach

• Dynamic Programming: The solution uses a dynamic programming approach to build a table (dp) where dp[i] represents the length of the longest divisible subset ending at index i
• The solution also maintains a table (prev_idx) to keep track of the previous element in the longest divisible subset ending at each index.

Complexity

• O(n^2), where n is the number of elements in the input array

Explanation

• The solution first sorts the input array and initializes the dp and prev_idx tables
• It then iterates over the array, updating the dp and prev_idx tables to build the longest divisible subset
• Finally, it iterates over the dp table to find the index of the longest divisible subset and constructs the answer vector by backtracking from that index.

Solution Code:

class Solution {
public:
    int dp[1001];
    int prev_idx[1001];
    vector largestDivisibleSubset(vector& nums) {
        // dp
        sort(nums.begin(), nums.end());
        for(int i = 0 ; i < nums.size(); i++){
            dp[i] = 1;
            prev_idx[i] = -1;
        }
        for(int i = 0 ; i < nums.size(); i++){
            for(int j = i - 1 ; j >= 0; j--){
                if((dp[j]+1) > dp[i] && (nums[i] % nums[j]) == 0){
                    dp[i] = dp[j] + 1;
                    prev_idx[i] = j;
                }
            }
        }
        int max = 0;
        int idx = 0;
        for(int i = 0; i < nums.size(); i++){
            if(max < dp[i]){
                max = dp[i];
                idx = i;
            }
        }
        vector ans;
        while(idx != -1){
            ans.push_back(nums[idx]);
            idx = prev_idx[idx];
        }
        return ans;
    }
};