LeetCode简单题之找到和最大的长度为 K 的子序列

题目

给你一个整数数组 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）

解题思路

  这个题所要求的结果数组在原数组中是不需要连续的，这样就大大降低了题目的难度，所以第一步可以先将给定的数组排序，然后取出最大的几个元素和它们的下标，然后在截取符合条件的结果并返回正确的在原数组中的先后顺序。

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]
1
2
3
4
5

  当然这道题其实是不需要完全将排序做完的，最好的方法就是用选择排序将符合条件的k个选出来后便不再继续排序。

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)]
1
2
3
4
5
6
7
8
9
10
11
12