题目大意：
非递增顺序的最小子序列
给你一个数组 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 <= 5001 <= nums[i] <= 100
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1403
解题思路分析：
虽然这是一道Easy题目，但还是需要我们稍微动一下脑筋。首先考虑2点：
- 我们将数组分成任意两部分，如果要保证其中一个部分的数字和大于另一部分，那么该部分数字和一定大于数组中所有数字之和的一半。
- 题目要求长度最小的符合条件的子序列，长度小也就代表子序列中的元素个数少，既然个数要求尽量少，那么每个元素的数值就要保证尽量大才行。
解题时，我们先对数组进行排序。然后假设数组长度是n，我们将数组分成长度为0和n两个部分，此时长度为n的这个部分的元素和一定大于长度为0的部分（废话）。然后我们开始循环尝试从长度为n的部分中减去一个最小值，之后查看剩下的元素和是否大于数组总和的一半，如果大于，则重复上述过程。反之退出循环。剩下的元素即是我们要求的结果。
当然这道题反过来做也可行，我们向长度为0的部分加入一个最大值，如果当前数值和小于等于数组所有元素和的一半，继续从剩下的元素中找一个最大值添加进当前子序列。当子序列中元素数字和大于所有元素和的一半时，当前子序列即是返回结果。
总结一下，本题实际上是在利用贪心算法解题。如果暴力解我们需要遍历所有分组情况，然后再找到一个最优解。贪心算法的核心是，我们利用数组中前n大的数字组成的子序列一定是满足条件下序列长度最小的结果。
实现代码：
public List<Integer> minSubsequence(int[] nums) {
Arrays.sort(nums); // 排序数组
int sum=0; // 数组中元素和
for(int n : nums) sum+=n;
int half = sum/2+1; // 元素和的一半
// 返回结果
List<Integer> res = new ArrayList<>();
// 序列元素和
int sequenceSum=0;
for(int i=nums.length-1;i>=0;i--){
// 将当前最大元素加入到返回结果
res.add(nums[i]);
// 累加子序列元素和
sequenceSum+=nums[i];
// 如果子序列元素和大于数组所有元素和的一半，退出循环
if(sequenceSum>=half) break;
}
return res;
} 本题解法执行时间为3ms。
Runtime: 3 ms, faster than 98.60% of Java online submissions for Minimum Subsequence in Non-Increasing Order.
Memory Usage: 39.1 MB, less than 100.00% of Java online submissions for Minimum Subsequence in Non-Increasing Order.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1403-minimum-subsequence-in-non-increasing-order-解题思路分析/