leetcode1403之非递增顺序的最小子序列

题目描述：

给你一个数组 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] 是满足题意的最小子序列。注意，元素按非递增顺序返回。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-subsequence-in-non-increasing-order
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码如下：

 1 def minSeq(nums):
 2     result = 0
 3     result_array = []
 4     while nums:
 5         max_item = max(nums)
 6         result += max_item
 7         if result > sum(nums) - max_item:
 8             result_array.append(max_item)
 9             return result_array
10         else:
11             result_array.append(max_item)
12             nums.remove(max_item)
13 
14 
15 print("--------------测试minSeq()-------------")
16 nums = [4, 3, 7, 9, 6]
17 result_array = minSeq(nums)
18 print("result_array=", result_array)
19 
20 
21 def minSuq1(nums):
22     '''
23 
24     :param nums:
25     :return:
26     '''
27     result = 0
28     result_array = []
29     while result <= sum(nums):
30         max_item = max(nums)
31         result += max_item
32         result_array.append(max_item)
33         nums.remove(max_item)
34 
35     return result_array
36 
37 
38 print("--------------测试minSqu1()---------------")
39 nums = [4, 3, 7, 9, 6]
40 result_array = minSuq1(nums)
41 print("result_array=", result_array)

输出：

--------------测试minSeq()-------------
result_array= [9, 7]
--------------测试minSqu1()---------------
result_array= [9, 7]

总结：上述给出了两种方法，从思想来说，两种大同小异，可以看作同一种方法，只是方法2看起来更简洁。两种方法思路都是逐一找出nums数组中的最大值进行累加，然后与nums剩余元素之和进行比较，若满足题设，则返回；反之继续累加，直至满足条件!