LeetCode 1403 非递增顺序的最小子序列[贪心] HERODING的LeetCode之路

解题思路：
首先获取数组的和，然后对数组进行排序，由于尽可能找长度最小和大于原数组和一半的序列，所以从大往小找即可，代码如下：

class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        int n = nums.size();
        int total = accumulate(nums.begin(), nums.end(), 0);
        sort(nums.begin(), nums.end());
        vector<int> ans;
        int cur = 0;
        for(int i = n - 1; i >= 0; i --) {
            if(cur <= total / 2) {
                ans.emplace_back(nums[i]);
                cur += nums[i];
            } else {
                break;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19