[Leetcode/Heap] 2099. Find Subsequence of Length K With the Largest Sum

 

You can solve this problem by:

1. Finding the k largest elements based on value (to maximize the sum).
2. Preserving their original order in the array (since it's a subsequence).

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        # Step 1: Pair each element with its original index
        indexed_nums = list(enumerate(nums))
        
        # Step 2: Select the k largest elements based on value
        # heapq.nlargest will return tuples (index, value) based on value
        largest_k = heapq.nlargest(k, indexed_nums, key=lambda x: x[1])
        
        # Step 3: Sort the selected k elements by their original index to preserve order
        largest_k.sort(key=lambda x: x[0])
        
        # Step 4: Extract and return only the values
        return [num for idx, num in largest_k]

---

heapq.nlargest()

heapq.nlargest(k, iterable, key=None)

• k → How many largest elements you want
• iterable → The list or data you’re working with
• key (optional) → A function that tells Python how to compare the elements

🧠 What it does:

Instead of sorting the whole list (which takes time), it uses a heap (a kind of binary tree structure) behind the scenes to quickly find the top k largest elements.

It’s like saying:

“Give me the top k scores in the list.”

✅ Example 1: Simple usage

import heapq nums = [5, 1, 8, 3, 10]
top3 = heapq.nlargest(3, nums)
print(top3)

[10, 8, 5]

✅ Example 2: With key (like sorting by a property)

Imagine a list of tuples like this:

students = [("Alice", 92), ("Bob", 85), ("Carol", 97)]

 

If you want the top 2 students by score (the second item), you can do:

top_students = heapq.nlargest(2, students, key=lambda x: x[1])
print(top_students)

[("Carol", 97), ("Alice", 92)]

 

 

🔥 Why use heapq.nlargest() instead of sorted()?

heapq.nlargest()	sorted()
Faster for large lists with small k	Slower — always sorts full list
Uses a heap internally	Uses full sort