Solution: Find Subsequence of Length K with the Largest Sum

Statement

You are given an integer array nums and an integer k. Your task is to find a subsequenceA subsequence is an array derived from another array by deleting some or no elements while preserving the order of the remaining elements. of nums of length k that has the largest possible sum.

Constraints:

• $1 \leq$ nums.length $\leq 1000$

• $-10^5 \leq$ nums[i] $\leq 10^5$

• $1 \leq$ k $\leq$ nums.length

Solution

To solve this problem, we use a min heap to track the largest k elements as we iterate through the array. This approach ensures that we always maintain the largest elements while discarding smaller ones. After populating the heap with the k largest elements, we extract them into a list. Since the heap maintains no particular order related to the original indexes, we then sort the list by the original indexes of the elements to preserve the relative order of those k elements in the input array. Finally, we extract the values from the sorted list and return them as the subsequence.

The steps of the algorithm are as follows:

1. Create an empty minHeap to store pairs of elements and their corresponding indexes.

2. For each element in the nums array, perform the following:

   1. Push the current element and its index i as a tuple into the minHeap using minHeap.Insert.

   2. If the size of minHeap exceeds k, then remove the smallest element from the heap using minHeap.RemoveMin(). This keeps only the largest k elements.

3. After the loop finishes, the heap contains the k largest elements. However, since we need to return the subsequence in the same order as the original array, the elements in the heap are sorted based on their original indexes (x[1]). This ensures that the output subsequence preserves the relative order from nums.

4. The final result list is created by extracting only the element values (x[0]) from the sorted list of tuples. This gives the subsequence with the largest sum of length k, in the correct order.

5. Return the result list containing the k largest elements in their original order.

Let’s look at the following illustration to get a better understanding of the solution: