Leetcode Largest Divisible Subset problem solution

In this Leetcode Largest Divisible Subset problem solution You are given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:

answer[i] % answer[j] == 0, or

answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

Problem solution in Python.

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        
        n=len(nums)    
        #base case
        if n==1 or n==0:
            return nums
        #sorting to apply lis
        nums.sort()
        
        #DP table
        lis=[1 for _ in range(n)]
        
        #table to store indexes 
        pre=[-1 for _ in range(n)]
        
        max=0
        index=-1
        for i in range(0,n):
            for j in range(i-1,-1,-1):
                if nums[i]%nums[j]==0:
                    if lis[i]<lis[j]+1:
                        lis[i]=lis[j]+1
                        pre[i]=j
            if lis[i]>max:
                max=lis[i]
                index=i
                
        subset=[]
        while index!=-1:
            subset.insert(0,nums[index])
            index=pre[index]
            
        return subset

Problem solution in Java.

public List<Integer> largestDivisibleSubset(int[] nums) {
        
        List<Integer> ret = new ArrayList<Integer>();
        
        if (nums == null || nums.length == 0)
            return ret;
            
        Arrays.sort(nums);
        
        int[] dp = new int[nums.length];
        int[] prev = new int[nums.length];
        Arrays.fill(dp, 1);
        prev[0] = 0;
        
        for (int i = 1; i < nums.length; i++) {
            for (int j = i-1; j >= 0; j--) {
                if (nums[i] % nums[j] == 0) {
                
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        prev[i] = j;
                    }
                   
                }
            }
        }
        int maxIndex = 0;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }
        
        int len = dp[maxIndex];
        
        while (true) {
            ret.add(nums[maxIndex]);
            maxIndex = prev[maxIndex];
            
            if (--len <= 0)
                break;
        }
      
        return ret;

    }

Problem solution in C++.

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) {
            return vector<int>();
        }
        vector<int> dp(n, 1);
        vector<int> parent(n, -1);
        sort(nums.begin(), nums.end());
        for(int i=1;i<n;i++) {
            for(int j=0;j<i;j++) {
                if(nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j; 
                }
            }
        }
        int maxIndex = 0, maxLen = 0;
        for(int i=0;i<n;i++) {
            if(dp[i] > maxLen) {
                maxLen = dp[i];
                maxIndex = i;
            }
        }
        vector<int> ans(maxLen);
        int x = maxLen-1;
        while(maxIndex != -1) { 
            ans[x] = nums[maxIndex];
            maxIndex = parent[maxIndex];
            x--;
        }
        return ans;
    }
};

Problem solution in C.

int cmp(void* a,void* b){
    return *(int*)a-*(int*)b;
}
void func(int* nums, int numsSize,int* map,int* lens,int pre_index){
    if(numsSize==1||map[0]!=0){
        return;
    }
    for(int i=1;i<numsSize;i++){
        if(nums[i]%nums[0]==0){
            if(map[i]==0){
                func(&nums[i], numsSize-i,&map[i],&lens[i],pre_index+i);
            }
            if(lens[0]<lens[i]+1){
                map[0]=i+pre_index;
                lens[0]=lens[i]+1;
            }
        }
    }
}
int* largestDivisibleSubset(int* nums, int numsSize, int* returnSize){
     *returnSize=0;
    if(numsSize==0){
        return NULL;
    }
    qsort(nums,numsSize,sizeof(nums[0]),cmp);
    int* map=(int*)calloc(numsSize,sizeof(int));
    int* lens=(int*)calloc(numsSize,sizeof(int));
    int* ret=(int*)calloc(numsSize,sizeof(int));
    for(int i=0;i<numsSize-1;i++){
        if(map[i]!=0){
            continue;
        }
        func(&nums[i], numsSize-i,&map[i],&lens[i],i);
    }
    int index=0;
    for(int i=1;i<numsSize;i++){
        if(lens[i]>lens[index]){
            index=i;
        }
    }
    while(map[index]!=0){
        ret[(*returnSize)++]=nums[index];
        index=map[index];
    }
    ret[(*returnSize)++]=nums[index];
    return ret;
}