1403. 非递增顺序的最小子序列

题目描述：

给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。

如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。

与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。

注意，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。

测试用例：

示例 1：

输入：nums = [4,3,10,9,8]
输出：[10,9]
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。

示例 2：

输入：nums = [4,4,7,6,7]
输出：[7,7,6]
解释：子序列 [7,7] 的和为 14 ，不严格大于剩下的其他元素之和（14 = 4 + 4 + 6）。因此，[7,6,7] 是满足题意的最小子序列。注意，元素按非递增顺序返回。  

示例 3：

输入：nums = [6]
输出：[6]

限制及提示：

• 1 <= nums.length <= 500
• 1 <= nums[i] <= 100

---

解题分析及思路：

本题可以采用贪心的方法进行解答

对于数组 nums，需要将它分为两部分，一部分之和必须大于另一部分之和。那么可以采用贪心法。

取值的时候，取数组中剩余元素的最大值，并且累计之和小于原数组之和的一半时，继续取值，直到大于原数组之和的一半即可。

为了方便取到最大值，需要对原数组进行排序。

sort.Slice(nums, func(i, j int) bool {
    return nums[i] > nums[j]
})

然后，贪心的取值，先计算原数组和，然后在取值的时候与和的一半做比较

var sum int
for index := range nums {
    sum += nums[index]
}
sum >>= 1
var res []int
for index := range nums {
    sum -= nums[index]
    res = append(res, nums[index])
    if sum < 0 {
        break
    }
}

复杂度：

• 时间复杂度：O(nlogn)，排序所需时间
• 空间复杂度：O(logn)

执行结果：

• 执行用时：4 ms, 在所有 Go 提交中击败了93.48%的用户
• 内存消耗：3.2 MB, 在所有 Go 提交中击败了82.61%的用户