A pure-c dp solution


  • 0
    B
    static int compare(const void *a, const void *b) {
      return *(int*)a - *(int*)b;
    }
     
    typedef struct Node Node;
    
    struct Node {
        int pre;
        int count;
    };
     
    int* largestDivisibleSubset(int* nums, int numsSize, int* returnSize) {
        Node *dp;
        int i, j, maxNode, maxCount, *result;
        
        maxCount = 0;
        qsort (nums, numsSize, sizeof(int), compare); 
        if ((dp = malloc(sizeof(Node[numsSize]))) == NULL)
            return NULL;
        for (i = 0; i < numsSize; i++) {
            dp[i].count = 1;
            for (j = 0; j < i; j++) 
                if (nums[i] % nums[j] == 0 && dp[i].count < dp[j].count + 1) {
                    dp[i].pre = j;
                    dp[i].count = dp[j].count + 1;
                }
            if (maxCount < dp[i].count) {
                maxNode = i;
                maxCount = dp[i].count;
            }
        }
        
        *returnSize = maxCount;
        if ((result = malloc(sizeof(int[maxCount]))) == NULL)
            goto err;
        
        for (i = maxNode; maxCount > 0; i = dp[i].pre)
            result[--maxCount] = nums[i];
        
    err:
        if (dp)
            free(dp);
        return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.