#2099

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find Subsequence of Length K With the Largest Sum

Pick the k largest values, then restore their original order to build the maximum-sum subsequence correctly.

array hash table sorting heap priority queue

Problem Statement

You are given an integer array nums and an integer k, and you need a subsequence of length k whose total sum is as large as possible. The returned array must keep the same relative order as nums, because removing elements is allowed but reordering is not.

A direct example is nums = [2,1,3,3] with k = 2, where the best answer is [3,3] because those two values produce the largest possible sum. The main challenge in this problem is handling duplicates and preserving order after identifying which k numbers should be kept.

Examples

Example 1

Input: nums = [2,1,3,3], k = 2

Output: [3,3]

The subsequence has the largest sum of 3 + 3 = 6.

Example 2

Input: nums = [-1,-2,3,4], k = 3

Output: [-1,3,4]

The subsequence has the largest sum of -1 + 3 + 4 = 6.

Example 3

Input: nums = [3,4,3,3], k = 2

Output: [3,4]

The subsequence has the largest sum of 3 + 4 = 7. Another possible subsequence is [4, 3].

Constraints

1 <= nums.length <= 1000
-105 <= nums[i] <= 105
1 <= k <= nums.length

Solution Approach

Greedy target: choose the k biggest values

From a greedy perspective, the maximum-sum subsequence must contain the k largest elements from nums when counted with duplicates. Sort a copy of nums in descending order, take the first k values, and treat that multiset as the target selection.

Use a hash map to track how many times each chosen value is needed

Because duplicate values matter in LeetCode 2099, a plain set fails. Store frequency counts for the selected k values, such as needing two 3s and one -1, so the second pass knows exactly which occurrences still belong in the answer.

Scan the original array to rebuild the subsequence order

Walk through nums from left to right and append a number only if its remaining count in the hash map is positive. Decrease the count each time you use one. This preserves subsequence order and guarantees the answer length is exactly k while matching the maximum-sum selection.

Complexity Analysis

Metric	Value
Time	O(n \log n)
Space	O(n)

Sorting dominates the work, so the time complexity is O(n \log n). The extra space is O(n) in the straightforward version because you store a copied array, the frequency map for the chosen values, and the output subsequence.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

Sorting the whole array and returning the first k values directly breaks the subsequence requirement because it loses original order.
Using a set for chosen numbers fails when the optimal answer needs repeated values, such as taking both 3s in [2,1,3,3].
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.

Follow-up variants

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.
Store selected indices by sorting pairs of value and index, choosing the best k pairs, and sorting those indices before output.
If asked for the maximum sum only, the subsequence-order rebuild disappears and the task becomes just tracking the top k values.

FAQ

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.

terminal

Solution

Solution 1: Sorting

First, we create an index array $\textit{idx}$, where each element is an index of the array $\textit{nums}$. Then, we sort the index array $\textit{idx}$ based on the values in $\textit{nums}$, with the sorting rule being $\textit{nums}[i] < \textit{nums}[j]$, where $i$ and $j$ are two indices in the index array $\textit{idx}$.

1

2

3

4

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)]

Continue Practicing

#2342 max sum of a pair with equal sum of digits #2357 make array zero by subtracting equal amounts #2402 meeting rooms iii