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
kwith 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
-
Find the Threshold: Use
nth_element(or min-heap) to determine the smallest number in the topkvalues. - Count Frequency: Count how many values are strictly greater than the threshold and how many equal to it can still be selected.
- 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
Om Shree | Sciencx (2025-06-28T00:27:37+00:00) 🍸 Selecting the Largest Sum Subsequence of Length K – LeetCode 2099 (C++ | JavaScript | Python ). Retrieved from https://www.scien.cx/2025/06/28/%f0%9f%8d%b8-selecting-the-largest-sum-subsequence-of-length-k-leetcode-2099-c-javascript-python/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.