LeetCode simple problem to find the subsequence of length K with the largest sum

题目

给你一个整数数组 nums 和一个整数 k .你需要找到 nums 中长度为 k 的 子序列 ,且这个子序列的 和最大 .

请你返回 任意 一个长度为 k 的整数子序列.

子序列 定义为从一个数组里删除一些元素后,不改变剩下元素的顺序得到的数组.

示例 1：

输入：nums = [2,1,3,3], k = 2
输出：[3,3]
解释：
子序列有最大和：3 + 3 = 6 .
示例 2：

输入：nums = [-1,-2,3,4], k = 3
输出：[-1,3,4]
解释：
子序列有最大和：-1 + 3 + 4 = 6 .
示例 3：

输入：nums = [3,4,3,3], k = 2
输出：[3,4]
解释：
子序列有最大和：3 + 4 = 7 .
另一个可行的子序列为 [4, 3] .

提示：

1 <= nums.length <= 1000
-10^5 <= nums[i] <= 10 ^5
1 <= k <= nums.length

来源：力扣（LeetCode）

解题思路

  The result array required by this question does not need to be contiguous in the original array,This greatly reduces the difficulty of the problem,So the first step is to sort the given array first,Then take the largest elements and their subscripts,Then intercept the results that meet the conditions and return the correct sequence in the original array.

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        new_nums=sorted(enumerate(nums),key=lambda x:-x[1])
        ans=sorted(new_nums[0:k],key=lambda x:x[0])
        return [i[1] for i in ans]

  Of course, this question does not need to be completely sorted,The best way to do this is to use selection sort to match the conditionskAfter one is selected, it will not continue to sort.

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        ans=[]
        for i in range(k):
            MAX,index=-float('inf'),-1
            for j in enumerate(nums):
                if j[1]!=None:
                    if j[1]>MAX:
                        MAX,index=j[1],j[0]
            ans.append((index,MAX))
            nums[index]=None
        return [i[1] for i in sorted(ans)]