subsequenceOfLength.txt

2099. Find Subsequence of Length K With the Largest Sum

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.

class Solution {
public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        priority_queue<pair<int,int> , vector<pair<int,int>>,greater<pair<int,int>> > pq;

        for(int i = 0; i < nums.size(); i++){
            pq.push({nums[i],i});
            if(pq.size() > k){
                pq.pop();
            }
        }

        priority_queue<pair<int,int> , vector<pair<int,int>>,greater<pair<int,int>> > temp;

        while(!pq.empty()){
            temp.push({pq.top().second,pq.top().first});
            pq.pop();
        }

        vector<int> ans;
        while(!temp.empty()){
            ans.push_back(temp.top().second);
            temp.pop();
        }

        return ans;
    }
};