368.最大整除子集

 

　　给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
　　answer[i] % answer[j] == 0 ，或     answer[j] % answer[i] == 0；
　　如果存在多个有效解子集，返回其中任何一个均可。

示例 1：

　　输入：nums = [1,2,3]
　　输出：[1,2]
　　解释：[1,3] 也会被视为正确答案。
示例 2：

　　输入：nums = [1,2,4,8]
　　输出：[1,2,4,8]

提示：

　　1 <= nums.length <= 1000
　　1 <= nums[i] <= 2 * 109
　　nums 中的所有整数 互不相同

先找出那个集合，找的方法和找最长上升子序列方法一样，DP问题而且状态转移方程 也与其一样；找到最大max = dp[i] 的值，这也是最后returnsize的值，也是最后答案res数组的长度；

最后解决如何把集合放进res数组，可以是倒着往前搜，找到符合条件的放进数组里；

nums	2	3	5	25	30	50
dp	1	1	1	2	2	3

具体符合条件的就是先找到max，放入数组，然后max - 1,再一次次找 = max的，而且要找到的的数和前一个是整除关系；就比如说  50  是数组最后一个数，而 30 就不能是倒数第二个数！

int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}
int* largestDivisibleSubset(int* nums, int numsSize, int* returnSize){
    qsort(nums, numsSize, sizeof(nums[0]), cmp); //排序
    int i, j, dp[1005], max = -999999;
    int t, x;//x 记录nums[i]的数值;用于判断是否整除for(i = 0; i < numsSize; i++){
        dp[i] = 1;
        for(j = i - 1; j >= 0; j--){
            if(nums[i] % nums[j] == 0){
                 dp[i] = fmax(dp[i], dp[j] + 1);
            }
        }
        if(max < dp[i]){
            max = dp[i];
            x = nums[i];
        }
    }
    int *res = malloc(sizeof(int) * max);
    t = max;
    if(max == 1){//小优化；
        res[0] = nums[0];
        *returnSize = max;
        return res;
    }
    for(i = numsSize - 1; i >= 0; i--){
        if(dp[i] == t && x % nums[i] == 0){
            res[--t] = nums[i];
            x = nums[i];
        }
    }
    *returnSize = max;
    return res;
}