What is the main idea behind Find Subsequence of Length K With the Largest Sum?

Choose the k largest values globally, then scan the original array and keep those values in their original order. That combination gives the maximum sum while still producing a valid subsequence.

Why is array scanning plus hash lookup a good pattern for this problem?

The scan restores subsequence order, and the hash lookup tells you whether the current value is still needed. This is especially important when the selected top k values include duplicates.

Why can the answer be [3,4] or [4,3] in some cases?

Only outputs that preserve the original index order are valid subsequences. In nums = [3,4,3,3] with k = 2, both [3,4] and [4,3] can be valid maximum-sum subsequences because each matches a different valid pair of indices.

Can I solve LeetCode 2099 without sorting the entire array?

Yes. You can keep a min-heap of size k to track the k largest values, then use a frequency map and a final scan to rebuild the subsequence in order.

What is the easiest bug to make on this problem?

The most common bug is choosing the right values but returning them in sorted order instead of original order. Another frequent mistake is using a set and losing duplicate elements that should appear multiple times in the result.

#2099

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

找到和最大的长度为 K 的子序列

给你一个整数数组 nums 和一个整数 k 。你需要找到 nums 中长度为 k 的子序列，且这个子序列的和最大。请你返回任意一个长度为 k 的整数子序列。子序列定义为从一个数组里删除一些元素后，不改变剩下元素的顺序得到的数组。示例 1：输入： nums = [2,1,3,3]…

数组哈希表排序堆（优先队列）

题目描述

给你一个整数数组 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⁵ <= nums[i] <= 10⁵
1 <= k <= nums.length

lightbulb

解题思路

方法一：排序

我们先创建一个索引数组 $\textit{idx}$ ，数组中的每个元素是数组 $\textit{nums}$ 的下标。然后我们根据数组 $\textit{nums}$ 的值对索引数组 $\textit{idx}$ 进行排序，排序的规则是 $\textit{nums}[i] < \textit{nums}[j]$ ，其中 $i$ 和 $j$ 是索引数组 $\textit{idx}$ 中的两个下标。

排序完成后，我们取索引数组 $\textit{idx}$ 的最后 $k$ 个元素，这 $k$ 个元素对应的就是数组 $\textit{nums}$ 中最大的 $k$ 个元素。然后我们对这 $k$ 个下标进行排序，得到的就是最大的 $k$ 个元素在数组 $\textit{nums}$ 中的顺序。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        idx = sorted(range(len(nums)), key=lambda i: nums[i])[-k:]
        return [nums[i] for i in sorted(idx)]

speed

复杂度分析

指标	值
时间	O(n \log n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
They ask what the greedy choice is before discussing implementation, which points to selecting the k largest values first.
question_mark
They emphasize subsequence instead of subset, which is a signal that original index order must be restored after selection.
question_mark
They bring up duplicate numbers like [3,4,3,3], which usually means a hash map of counts is safer than a set.

warning

常见陷阱

外企场景

error
Sorting the whole array and returning the first k values directly breaks the subsequence requirement because it loses original order.
error
Using a set for chosen numbers fails when the optimal answer needs repeated values, such as taking both 3s in [2,1,3,3].
error
Picking the first k large-looking numbers during one scan can miss a later better value, so greedy must be based on the global top k values, not local choices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Use a min-heap of size k instead of sorting all values to keep only the current top k elements, then rebuild order with counts.
arrow_right_alt
Store selected indices by sorting pairs of value and index, choosing the best k pairs, and sorting those indices before output.
arrow_right_alt
If asked for the maximum sum only, the subsequence-order rebuild disappears and the task becomes just tracking the top k values.

help

常见问题

外企场景

继续练习

#2342 数位和相等数对的最大和 #2357 使数组中所有元素都等于零 #2402 会议室 III