Find Subsequence of Length K With the Largest Sum
We use quick select to determine the klargest element. The idea is that all elements bigger than klargest will be in the result array.
What about the klargest element itself? Right, duplicates could stir some trouble. So, we count how many times (cnt) klargest elements appear within k numbers.
Step 1: Finding the klargest Element
In the problem, we want to find a subsequence of k
numbers from the array that has the largest sum. To do this, we use a technique called “quick select” to find the klargest element in the array. This technique allows us to identify the klargest element quickly without having to sort the entire array.
Step 2: Selecting Elements Bigger Than the klargest
Once we have found the klargest element, we know that all the elements bigger than this value must be part of our result, as they contribute to the largest sum.
Step 3: Handling Duplicates of the klargest Element
The klargest element itself might appear more than once in the array. We want to include the exact number of klargest elements that appear in the top k
numbers. For this purpose, we count how many times the klargest element appears within the top k
numbers (let’s call this count cnt
).
Putting It All Together
We then iterate through the original array and add the elements to our result if:
 They are bigger than the klargest element (since they contribute to a larger sum)
 They are equal to the klargest element, and the count (
cnt
) of this element is not yet exhausted (since we want to include the exact number of klargest elements that are part of the topk
)
Example
Let’s say our array is [2, 3, 3, 4]
, and k = 2
. The klargest element is 3
, and it appears once within the top 2 numbers. In our result, we want to include all numbers greater than 3
(which is 4
) and one occurrence of 3
. So our result would be [3, 4]
.
Key Takeaways
 We quickly find the klargest element without sorting the whole array.
 We include all elements bigger than the klargest in our result.
 We handle the klargest element itself carefully by considering its duplicates within the top
k
numbers.


This code creates a subsequence of nums
of length k
that has the largest sum, following the same logic as the provided C++ code. It first sorts the largest k
elements of nums
and then iterates through the original nums
array, adding elements to the result if they meet the condition defined in the original code.