🍸 Selecting the Largest Sum Subsequence of Length K – LeetCode 2099 (C++ | JavaScript | Python )

This content originally appeared on DEV Community and was authored by Om Shree

Hey, algorithm enthusiasts!

Today, we explore a clean and greedy approach to one of LeetCode’s simpler but clever problems: “2099. Find Subsequence of Length K With the Largest Sum.”

At first glance, it feels like a straightforward sorting challenge, but what makes this interesting is how we maintain the original order of the subsequence while still capturing the top k values. Let’s break it down methodically.

Problem Summary

Input:

• An integer array nums
• An integer k

Goal:

• Find a subsequence of length k with the largest sum.
• The subsequence must preserve the relative ordering of the original array.

Definition:

• A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements.

Intuition

To maximize the sum of the subsequence:

• We want the k largest elements from the array.
• But since relative order matters, we can’t just sort and slice.

Key Insight:

• Track the indices of the k largest values.
• Reconstruct the result by scanning the original array and selecting only those values.

This is a classic case where combining a min-heap selection (or nth_element) with sorting by indices lets us optimize both for value and order.

Approach

1. Find the Threshold: Use nth_element (or min-heap) to determine the smallest number in the top k values.
2. Count Frequency: Count how many values are strictly greater than the threshold and how many equal to it can still be selected.
3. Reconstruct Subsequence: Traverse the original array and greedily add eligible values.

C++ Code

class Solution {
 public:
  vector<int> maxSubsequence(vector<int>& nums, int k) {
    vector<int> ans;
    vector<int> arr(nums);
    nth_element(arr.begin(), arr.end() - k, arr.end());
    const int threshold = arr[arr.size() - k];
    const int larger =
        ranges::count_if(nums, [&](int num) { return num > threshold; });
    int equal = k - larger;

    for (const int num : nums)
      if (num > threshold) {
        ans.push_back(num);
      } else if (num == threshold && equal) {
        ans.push_back(num);
        --equal;
      }

    return ans;
  }
};

JavaScript Code

var maxSubsequence = function(nums, k) {
    const arr = [...nums].sort((a, b) => b - a).slice(0, k);
    const freq = new Map();

    for (let num of arr)
        freq.set(num, (freq.get(num) || 0) + 1);

    const res = [];
    for (let num of nums) {
        if (freq.get(num)) {
            res.push(num);
            freq.set(num, freq.get(num) - 1);
        }
        if (res.length === k) break;
    }
    return res;
};

Python Code

def maxSubsequence(nums, k):
    import heapq
    arr = heapq.nlargest(k, nums)
    count = collections.Counter(arr)
    res = []

    for num in nums:
        if count[num]:
            res.append(num)
            count[num] -= 1
        if len(res) == k:
            break

    return res

Key Notes

• Time Complexity: O(n) for selection + O(n) for reconstruction
• Space Complexity: O(n) for auxiliary arrays/counters
• Carefully manage duplicates at the threshold value.
• Preserve order during reconstruction by processing original input.

Final Thoughts

This is a great example of blending greedy logic with practical selection techniques like nth_element or heap manipulation. Although it’s categorized as “Easy”, managing the edge cases (like duplicate threshold elements) adds depth to the problem.

Keep learning and stay sharp!

Happy coding!

This content originally appeared on DEV Community and was authored by Om Shree