1 class Solution: 2 def minSubsequence(self, nums: 'List[int]') -> 'List[int]': 3 nums = sorted(nums,reverse=True) 4 n = len(nums) 5 if n == 1: 6 return nums 7 sums = 0 8 presum = [0] * (n+1) 9 10 for i in range(n): 11 sums += nums[i] 12 presum[i+1] = presum[i] + nums[i] 13 print(sums,presum) 14 for i in range(n): 15 if presum[i+1] > sums - presum[i+1]: 16 return nums[:i+1]
算法思路:贪心算法。
先将数组倒序排序,计算前序和数组。
然后再一次遍历,每次计算前序和与剩余部分的大小,当首次出现前序和大于剩余部分和的时候,即为所求。