# Find Subsequence of Length K With the Largest Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum)
Canonical: https://scaleengineer.com/dsa/problems/find-subsequence-of-length-k-with-the-largest-sum
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Heap (Priority Queue)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Oracle](https://scaleengineer.com/companies/oracle)
---
## Problem
You are given an integer array `nums` and an integer `k`. You want to find a **subsequence** of `nums` of length `k` that has the **largest** sum.

Return_**any** such subsequence as an integer array of length_ `k`.

A **subsequence** is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

**Example 1:**

**Input:** nums = [2,1,3,3], k = 2
**Output:** [3,3]
**Explanation:**
The subsequence has the largest sum of 3 + 3 = 6.

**Example 2:**

**Input:** nums = [-1,-2,3,4], k = 3
**Output:** [-1,3,4]
**Explanation:** 
The subsequence has the largest sum of -1 + 3 + 4 = 6.

**Example 3:**

**Input:** nums = [3,4,3,3], k = 2
**Output:** [3,4]
**Explanation:**
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`

# Approaches
## Sorting with Index Preservation
The core idea is that the subsequence with the largest sum must consist of the `k` largest elements from the original array. A straightforward way to find these elements is to sort the array. However, sorting the array directly would lose the original relative order of the elements, which is a requirement for a subsequence. To overcome this, we can store each element along with its original index, sort based on the element's value, select the top `k` elements, and then restore their original order by sorting them again based on their original indices.
**Time:** O(n log n) - The dominant step is sorting the n elements, which takes O(n log n). Creating the indexed array is O(n), and sorting the k elements takes O(k log k). · **Space:** O(n) - We need an auxiliary array of size n to store the (value, index) pairs.
**Pros:** Relatively simple to understand and implement.; The O(n log n) performance is guaranteed and is efficient enough for the given constraints.
**Cons:** Not the most optimal solution as it sorts the entire array, which is more work than necessary.; Requires O(n) auxiliary space, which is more than some more optimized approaches.
### Explanation
This method ensures we identify the `k` largest values while being able to reconstruct their original relative ordering. 

Here's the breakdown of the algorithm:
1.  **Create Indexed Pairs**: We first iterate through the input array `nums` and create a new data structure, typically a 2D array or a list of custom objects. Each element in this structure will hold two pieces of information: the number itself (`nums[i]`) and its original position in the array (`i`).
2.  **Sort by Value**: We then perform a sort on this new structure. The sorting criterion is the value of the number, in descending order. This brings the largest numbers to the front.
3.  **Select Top K**: After sorting, the first `k` elements in our structure are the `k` largest values from the original array. We select these `k` pairs.
4.  **Sort by Index**: These `k` pairs are now sorted by value, not by their original position. To restore the subsequence order, we perform a second sort on just these `k` pairs, this time using their original index as the key, in ascending order.
5.  **Construct Result**: Finally, we iterate through the `k` index-sorted pairs and extract just the values to build our final result array.

```java
import java.util.Arrays;

class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        int n = nums.length;
        // 1. Store pairs of (value, index)
        int[][] indexedNums = new int[n][2];
        for (int i = 0; i < n; i++) {
            indexedNums[i][0] = nums[i];
            indexedNums[i][1] = i;
        }

        // 2. Sort by value in descending order
        Arrays.sort(indexedNums, (a, b) -> b[0] - a[0]);

        // 3. Take the top k elements
        int[][] topK = new int[k][2];
        for (int i = 0; i < k; i++) {
            topK[i] = indexedNums[i];
        }

        // 4. Sort the top k elements by their original index
        Arrays.sort(topK, (a, b) -> a[1] - b[1]);

        // 5. Extract the values to form the result subsequence
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = topK[i][0];
        }

        return result;
    }
}
```
### Algorithm
- Create a 2D array or a list of objects to store pairs of `(value, original_index)` for each element in `nums`.
- Sort these pairs in descending order based on the `value`.
- Select the first `k` pairs from the sorted list. These represent the `k` largest elements.
- Sort these `k` pairs in ascending order based on their `original_index` to restore the subsequence order.
- Create the final result array by extracting the `value` from each of the `k` index-sorted pairs.

## Using a Min-Heap (Priority Queue)
This approach improves upon sorting by finding the `k` largest elements more efficiently. Instead of sorting the entire array, we can maintain a min-heap of size `k`. We iterate through the array, and for each element, we compare it with the smallest element in our heap (the root). If the current element is larger, we replace the root with the current element. After one pass, the heap contains the `k` largest elements. The challenge of preserving order is then solved by identifying which elements from the original array belong to this set of `k` largest values using a frequency map.
**Time:** O(n log k) - Iterating through n elements with heap operations taking O(log k) each. The final scan is O(n). · **Space:** O(k) - The heap stores at most k+1 elements, and the frequency map stores at most k unique elements.
**Pros:** More efficient than the O(n log n) sorting approach, especially when k is much smaller than n.; Uses less auxiliary space (O(k)) compared to the sorting approach (O(n)).
**Cons:** Slightly more complex to reason about than the sorting approach, especially regarding the handling of duplicate values.
### Explanation
This method avoids a full `O(n log n)` sort by using a data structure optimized for finding top elements. 

Here's the breakdown of the algorithm:
1.  **Find K Largest with a Min-Heap**: We initialize a min-heap. We then iterate through the `nums` array. For each `num`, we add it to the heap. To ensure the heap only holds the largest elements seen so far, we check if its size has exceeded `k`. If it has, we `poll()` the smallest element, which is always at the root of a min-heap. This process takes `O(n log k)` time, as each of the `n` elements involves a heap operation that costs `O(log k)`.
2.  **Create Frequency Map**: Once we have the `k` largest elements in our heap, we need a way to pick them out from the original `nums` array while preserving order. A frequency map (like a `HashMap`) is perfect for this. We populate the map with the elements from the heap, counting how many times each value appears.
3.  **Build the Subsequence**: We iterate through the original `nums` array a second time. For each `num`, we check our frequency map. If the map contains the `num` and its associated count is positive, it means this is one of the `k` largest elements we're looking for. We add it to our result array and decrement its count in the map. This ensures we pick the correct number of duplicates and that they appear in their original relative order.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        // 1. Use a min-heap to find the k largest elements.
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // 2. Create a frequency map of the k largest elements.
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : minHeap) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // 3. Build the result subsequence by iterating through the original array.
        int[] result = new int[k];
        int index = 0;
        for (int num : nums) {
            if (freqMap.getOrDefault(num, 0) > 0) {
                result[index++] = num;
                freqMap.put(num, freqMap.get(num) - 1);
            }
        }
        return result;
    }
}
```
### Algorithm
- Use a min-heap (PriorityQueue in Java) of size `k` to find the `k` largest elements in a single pass.
- Iterate through `nums`. For each number, add it to the heap. If the heap's size grows larger than `k`, remove the smallest element (the root of the min-heap).
- After the pass, the heap contains the `k` largest elements. Create a frequency map of these elements.
- Iterate through the original `nums` array again. If the current number exists in the frequency map with a count greater than zero, add it to the result and decrement its count in the map.
- Return the constructed result array.

## Quickselect (Partitioning)
This is the most optimal approach on average. The problem can be reframed as finding the `(n-k)`-th smallest element in the array. Any element larger than this value must be part of the result. Elements equal to this value might be needed to fill the subsequence up to length `k`. The Quickselect algorithm (a variant of Quicksort) can find the `i`-th smallest/largest element in an array in average linear time.
**Time:** O(n) on average, O(n^2) in the worst case. Finding the k-th element via Quickselect is O(n) on average. The subsequent passes are also O(n). · **Space:** O(n) or O(log n) - A true Quickselect can be done in-place with O(log n) recursion stack space. The simplified code shown uses O(n) for a copy of the array.
**Pros:** Asymptotically the fastest approach with an average time complexity of O(n).; Highly efficient for large inputs where the difference between O(n) and O(n log k) is significant.
**Cons:** The worst-case time complexity is O(n^2), which can occur with consistently poor pivot choices in the Quickselect algorithm.; A proper implementation of Quickselect is more complex than using built-in sorting or heap data structures.
### Explanation
This approach leverages a powerful selection algorithm to achieve linear time complexity on average. Instead of fully sorting, we only find the specific element that partitions the array into the numbers we want and the numbers we don't.

Here's the breakdown of the algorithm:
1.  **Find the Threshold**: The key insight is that if we sort the array, the `k` largest elements would be at indices `n-k` through `n-1`. The element at index `n-k` is our cutoff point, or `threshold`. We don't need to fully sort to find this; we can use Quickselect to find the `(n-k)`-th smallest element in `O(n)` average time. For simplicity, the code below uses `Arrays.sort()`, which is `O(n log n)`, to find this threshold, but a true Quickselect implementation would be faster.
2.  **Count Elements**: Once we have the `threshold`, we need to handle duplicates. An element might be equal to the threshold, but we may or may not need it. We first count how many elements in the original array are strictly greater than the `threshold`. Let this be `count_greater`.
3.  **Determine Needed Duplicates**: The number of slots left in our subsequence is `k - count_greater`. This is exactly how many elements equal to the `threshold` we must include. Let this be `count_equal_needed`.
4.  **Construct Result**: We make a final pass through the original `nums` array to build the result in the correct order. We add any element that is greater than the `threshold`. We also add elements equal to the `threshold` until we have fulfilled our `count_equal_needed` quota.

```java
import java.util.Arrays;

class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        int n = nums.length;
        int[] sortedCopy = Arrays.copyOf(nums, n);
        // A true Quickselect would find this in O(n) average time.
        // For simplicity, we use sort which is O(n log n).
        Arrays.sort(sortedCopy);
        
        // 1. Find the threshold value.
        int threshold = sortedCopy[n - k];
        
        // 2. Count how many elements are > threshold.
        int countGreater = 0;
        for (int num : nums) {
            if (num > threshold) {
                countGreater++;
            }
        }
        
        // 3. Determine how many elements equal to the threshold are needed.
        int countEqualNeeded = k - countGreater;
        
        // 4. Build the result by iterating through the original array.
        int[] result = new int[k];
        int index = 0;
        for (int num : nums) {
            if (index == k) break;
            if (num > threshold) {
                result[index++] = num;
            } else if (num == threshold && countEqualNeeded > 0) {
                result[index++] = num;
                countEqualNeeded--;
            }
        }
        
        return result;
    }
}
```
### Algorithm
- The problem can be viewed as finding the `(n-k)`-th smallest element. Let's call this the `threshold`.
- Use the Quickselect algorithm to find this `threshold` value in `O(n)` average time.
- Count how many elements in the original array are strictly greater than the `threshold` (`count_greater`).
- Determine how many elements equal to the `threshold` are needed: `count_equal_needed = k - count_greater`.
- Iterate through the original `nums` array. Add any element `> threshold` to the result. Add any element `== threshold` to the result as long as `count_equal_needed > 0`, decrementing the count each time.
- This builds the final subsequence of length `k` in the correct order.

# Solutions
### Java

```java
class Solution {
public
  int[] maxSubsequence(int[] nums, int k) {
    int[] ans = new int[k];
    List<Integer> idx = new ArrayList<>();
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      idx.add(i);
    }
    idx.sort(Comparator.comparingInt(i->- nums[i]));
    int[] t = new int[k];
    for (int i = 0; i < k; ++i) {
      t[i] = idx.get(i);
    }
    Arrays.sort(t);
    for (int i = 0; i < k; ++i) {
      ans[i] = nums[t[i]];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> maxSubsequence(vector<int> &nums, int k) {
    int n = nums.size();
    vector<pair<int, int>> vals;
    for (int i = 0; i < n; ++i)
      vals.push_back({i, nums[i]});
    sort(vals.begin(), vals.end(),
         [&](auto x1, auto x2) { return x1.second > x2.second; });
    sort(vals.begin(), vals.begin() + k);
    vector<int> ans;
    for (int i = 0; i < k; ++i)
      ans.push_back(vals[i].second);
    return ans;
  }
};

```

### Python

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

```