LeetCode·每日一题·1403.非递增顺序的最小子序列·贪心

链接：https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order/solution/by-xun-ge-v-pray/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
题目需要得到 元素之和最大 长度最小 的子序列，并非子串，说明答案与位置无关，可以对原字符串进行处理，这里最简单的处理就是升序处理，因为我们需要最大元素
将数组元素升序处理，并统计数组元素和 max ，因为需要的 子序列的元素之和 严格 大于未包含在该子序列中的各元素之和 -> 我们取的子序列元素和*2应该刚刚好大于整个元素和
贪心思想：
每次取元素都从最大值开始，从而保证长度最短而元素之和最大

代码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int cmp(const void * a, const void * b)//升序
{
    return *(int *)a - *(int *)b;
}

int* minSubsequence(int* nums, int numsSize, int* returnSize){
    qsort(nums, numsSize, sizeof(int), cmp);
    int * ans = malloc(sizeof(int) * numsSize);
    int max = 0;//初始化变量
    for(int i = 0; i < numsSize; i++)//统计元素和
    {
        max += nums[i]; 
    }
    *returnSize = 0;
    int sum = 0;
    for(int i = numsSize-1; i >= 0; i--)//从最大值开始取元素
    {
        if(sum*2 > max)
            break;
        sum += nums[i];
        ans[(*returnSize)++] = nums[i];
    }
    return ans;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order/solution/by-xun-ge-v-pray/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。