Easy C++ Solution | Heaps | PQ | Understandable Code
Intuition\n Describe your first thoughts on how to solve this problem. \nThe maximum subsequence is determined based on the values in our input vector. \nWe can
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe maximum subsequence is determined based on the values in our input vector. \nWe can identify the maximum subsequence by utilizing a $$max-heap$$ to select the elements with the highest values and then $$sorting$$ the result based on the indices to maintain the original order.\nSince, using comparator sorting would lead to **O(nlogn)** time complexity and maintaining PQ will lead to **O(n)** space complextiy.\n\n--------------------------------\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1) **Priority Queue Setup**:\n-- Initialize a max heap ($$priority-queue$$) to store pairs of integers, where the first element is the $$value$$ from the input vector, and the second element is the $$index$$ of that value in the input vector.\n\n2) **Selecting Maximum Elements:**\n-- Iterate k times, each time extracting the top element (maximum value) from the priority queue. Store each extracted pair in the $$result$$ vector.\n\n3) **Sorting and Extracting Result**:\n-- $$Sort$$ the result vector based on the indices of the pairs, ensuring the original order of the elements. Construct final $$answer$$ by extracting the first element of each pair in the sorted result vector.\n\n4) **Result**:\n-- Return $$ans$$ containing the maximum subsequence of k-length.\n\n-------------------------\n\n# Complexity\n- Time complexity: O(N*logN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n-------------------------\n\n**If you find this solution helpful, consider giving it an upvote!**\n\n----------------------------------------------------------------------\n\n#### Do check out all other solutions posted by me here: https://github.com/adityajamwal02/Leetcode-Community-Solutions\n\n-------------------------------------------------------------------\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> maxSubsequence(vector<int>& nums, int k){\n        vector<pair<int,int>> result;\n        vector<int> ans;\n        priority_queue<pair<int,int>> pq;\n        for(int i=0;i<nums.size();i++) pq.push({nums[i],i});\n        for(int i=0;i<k;i++){\n            result.push_back(pq.top());\n            pq.pop();\n        } \n        sort(result.begin(),result.end(),[&](auto a, auto b){\n            return a.second<b.second;\n        });       \n        for(auto it : result) ans.push_back(it.first);\n    return ans;\n    }\n};\n```
['Heap (Priority Queue)', 'C++']