C++✅ || Beats 49%💯|| Min Heap Code💀💯|| Fast🔥💯
Intuition 🌟The task requires selecting the subsequence of length k with the maximum sum, while preserving the relative order of elements. The key insight is to
# Intuition 🌟  
The task requires selecting the subsequence of length `k` with the maximum sum, while preserving the relative order of elements. The key insight is to use a **min-heap** to efficiently track the top `k` elements by their values and then sort their indices to maintain order.
![Screenshot 2025-01-28 181629.png](https://assets.leetcode.com/users/images/3e55f426-cbfa-4e48-a5ab-93703dac9afb_1738068455.4415607.png)

# Approach 🚀  
1️⃣ **Push Elements with Indices into a Min-Heap**:  
   - Traverse the array and store each element along with its index in a **min-heap**.  
   - Maintain the heap size to `k` so that only the top `k` largest elements remain in the heap.  

2️⃣ **Extract Indices from the Heap**:  
   - Once the heap contains only the largest `k` elements, extract their indices.  

3️⃣ **Sort the Indices**:  
   - Sort the extracted indices to maintain the relative order of the elements in the subsequence.  

4️⃣ **Build the Result**:  
   - Use the sorted indices to construct the subsequence from the original array.  

# Complexity 📊  
- **Time complexity**:  
   - Traversing the array: $$O(n)$$.  
   - Heap operations for `k` elements: $$O(n \log{k})$$.  
   - Sorting the indices: $$O(k \log{k})$$.  
   - Total: $$O(n \log{k})$$.  

- **Space complexity**:  
   - Min-heap storage: $$O(k)$$.  
   - Indices and result arrays: $$O(k)$$.  
   - Total: $$O(k)$$.  

# Code 💻  
```cpp
class Solution {
public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        if (nums.size() == k) return nums; // If k equals array size, return the array

        // Min-heap to store the top k largest elements with their indices
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;

        for (int i = 0; i < nums.size(); i++) {
            minHeap.push({nums[i], i}); // Push element with index
            if (minHeap.size() > k) minHeap.pop(); // Keep only the largest k elements
        }

        vector<int> indices;
        // Extract indices from the heap
        while (!minHeap.empty()) {
            indices.push_back(minHeap.top().second);
            minHeap.pop();
        }

        sort(indices.begin(), indices.end()); // Sort indices to maintain relative order

        vector<int> ans;
        // Build the subsequence using sorted indices
        for (int idx : indices) {
            ans.push_back(nums[idx]);
        }

        return ans;
    }
};
```
![upvote.jpeg](https://assets.leetcode.com/users/images/64365b48-9187-4f4c-bf1b-aa0e2e4722ce_1738068441.4279892.jpeg)

['Array', 'Sorting', 'Heap (Priority Queue)', 'C++']