难度: Easy
给你一个整数数组 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-105 <= nums[i] <= 1051 <= k <= nums.length运行时间: 26 ms
内存: 16.1 MB
class Solution:
def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
if k == len(nums):
return nums
m = {}
for i in sorted(nums)[-k:]:
if i in m:
m[i] += 1
else:
m[i] = 1
r = []
i = 0
while len(r) != k:
if nums[i] in m and m[nums[i]] > 0:
r.append(nums[i])
m[nums[i]] -= 1
i += 1
return r
题解的思路主要是使用贪心算法来找到和最大的k个元素的子序列。首先对数组进行排序，然后取出最大的k个元素。这k个元素构成了和最大的子序列，但可能不保持原始顺序。为了保持原始顺序，我们使用一个哈希表记录这k个元素及其出现的次数。接着，我们遍历原始数组，按照原始顺序收集这些元素，直到收集完这k个元素。这样我们既保证了子序列的和最大，也保证了顺序。
时间复杂度: O(n log n)
空间复杂度: O(k)
class Solution:
def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
# 如果k等于数组长度，直接返回整个数组
if k == len(nums):
return nums
# 使用哈希表记录最大的k个元素及其出现次数
m = {}
for i in sorted(nums)[-k:]:
if i in m:
m[i] += 1
else:
m[i] = 1
# 遍历原数组，保持原有顺序收集元素
r = []
i = 0
while len(r) != k:
if nums[i] in m and m[nums[i]] > 0:
r.append(nums[i])
m[nums[i]] -= 1
i += 1
return r
当数组非常大或者元素难以比较时，排序步骤可能非常耗时或者不可行。此外，如果内存限制很严格，排序可能需要额外的存储空间。在这些情况下，可以考虑使用其他方法，如使用最小堆（优先队列）维护当前最大的k个元素。
哈希表可以快速地插入、检索和更新元素的出现次数，这对于此算法中的需求非常关键。使用数组跟踪出现次数可能导致效率问题，尤其是当元素范围很大或不是从0开始连续时，会有大量空间浪费或索引问题。哈希表提供了更灵活和空间高效的方式来处理这些问题。
算法通过哈希表中记录的元素出现次数来确保选择正确。即使元素是重复的，哈希表会记录每个元素应该出现的次数。遍历原始数组时，按照元素在数组中的顺序和哈希表中记录的次数来选择元素，这样可以确保即使是重复的元素也能正确地按照其出现次数被选择，从而最大化子序列的和。
如果nums数组为空或k为0，按照这种情况直接返回一个空列表即可。这是因为没有元素可选择，或者不需要选择任何元素来组成子序列。这种边界情况的处理是算法的一部分，确保算法的鲁棒性和完整性。