Find Subsequence of Length K With the Largest Sum

We use quick select to determine the k-largest element. The idea is that all elements bigger than k-largest will be in the result array.

What about the k-largest element itself? Right, duplicates could stir some trouble. So, we count how many times (cnt) k-largest elements appear within k numbers.

Step 1: Finding the k-largest 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 k-largest element in the array. This technique allows us to identify the k-largest element quickly without having to sort the entire array.

Step 2: Selecting Elements Bigger Than the k-largest

Once we have found the k-largest 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 k-largest Element

The k-largest element itself might appear more than once in the array. We want to include the exact number of k-largest elements that appear in the top k numbers. For this purpose, we count how many times the k-largest 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 k-largest element (since they contribute to a larger sum)
They are equal to the k-largest element, and the count (cnt) of this element is not yet exhausted (since we want to include the exact number of k-largest elements that are part of the top k)

Example

Let’s say our array is [2, 3, 3, 4], and k = 2. The k-largest 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 k-largest element without sorting the whole array.
We include all elements bigger than the k-largest in our result.
We handle the k-largest element itself carefully by considering its duplicates within the top k numbers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import Counter

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        if k == len(nums):
            return nums

        # Create a copy of nums and sort the first k elements
        v = nums.copy()
        v.sort(reverse=True)
        v = v[:k]

        # Create a result list
        res = []

        # Counter for occurrences of the k-th element in v
        cnt = v.count(v[k - 1])

        # Iterate through the original nums and build the result
        for num in nums:
            if num > v[k - 1] or (num == v[k - 1] and cnt > 0):
                res.append(num)
                if num == v[k - 1]:
                    cnt -= 1

        return res

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.