【week307-amazon】leetcode2386. 找出数组的第 K 大和

题目：
给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。

数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复）

返回数组的 第 k 大和 。

子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。

注意：空子序列的和视作 0 。

思路：

解答：

class Solution:
    def kSum(self, nums: List[int], k: int) -> int :
        sum=0
        for i, x in enumerate(nums):
            if x >= 0: sum += x
            else: nums[i] = -x
        nums.sort()
        #print(nums)
        h = [(0, 0)] 
        for _ in range(k - 1):
            s, i = heappop(h) #s为待减去的子序列的和
            if i < len(nums):
                heappush(h, (s + nums[i], i + 1))  # 保留 nums[i-1]
                if i: 
                    heappush(h, (s + nums[i] - nums[i - 1], i + 1))  # 不保留 nums[i-1]
            #print(i,h)
        return sum-h[0][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17