C++ / O(n) time quick select / O(nlogn) heap & map / three solution with explanation
Solution 1: quick select\nWe use quick select to get first k largest elements and then traverse these k elements to check how many same elements at the k-th lar
# Solution 1: quick select\nWe use quick select to get first k largest elements and then traverse these k elements to check how many same elements at the k-th largest. This is used to make sure we do not use more # than it should be in k largest elements.\n\n* time: `O(n)`\n* space: `O(n)`\n\n\n```\nclass Solution {\npublic:\n    vector<int> maxSubsequence(vector<int>& nums, int k) {\n        vector<int> res, tmp = nums;\n        nth_element(tmp.begin(), tmp.begin()+k-1, tmp.end(), [](const int &a, const int &b){\n            return a > b;\n        });\n        int kth = tmp[k-1], kcnt = 0;\n        for (int i = 0; i < k; ++i) {\n            kcnt += tmp[i] == kth;\n        }\n        for (int i = 0; i < nums.size(); ++i) {\n            if (k && (nums[i] > kth || nums[i] == kth && kcnt-- > 0)) {\n                res.push_back(nums[i]);\n                --k;\n            }\n        }\n        return res;\n    }\n};\n```\n# Solution 2\nWe can also use heap to get first k largest elements and feed them back to `res` .\n\n* time: `O(nlogn)`\n* space: `O(n)`\n\n\n```\nclass Solution {\npublic:\n    vector<int> maxSubsequence(vector<int>& nums, int k) {\n        vector<int> res, idx;\n        for (int i = 0; i < nums.size(); ++i) {\n            idx.push_back(i);\n        }\n        auto comp = [&nums](const int &a, const int &b) {\n            return nums[a] > nums[b];\n        };\n        priority_queue<int, vector<int>, decltype(comp)> que1(comp);\n        priority_queue<int, vector<int>, greater<int>> que2;\n        for (int i = 0; i < nums.size(); ++i) {\n            que1.push(i);\n            if (que1.size() > k) {\n                que1.pop();\n            }\n        }\n        while (que1.size()) {\n            que2.push(que1.top());\n            que1.pop();\n        }\n        while (que2.size()) {\n            res.push_back(nums[que2.top()]);\n            que2.pop();\n        }\n        return res;\n    }\n};\n```\n# Solution 3\nUsing ordered map, we easily find k largest elements and save them into this map.\n\n* time: `O(nlogn)`\n* space: `O(n)`\n\n\n```\nclass Solution {\npublic:\n    vector<int> maxSubsequence(vector<int>& nums, int k) {\n        vector<int> res;\n        map<int,int> map;\n        for (int i = 0; i < nums.size(); ++i) {\n            ++map[nums[i]];\n            if (i >= k) {\n                if (!--map.begin()->second) {\n                    map.erase(map.begin());\n                }\n            }\n        }\n        for (auto &num: nums) {\n            if (map.find(num) != map.end()) {\n                res.push_back(num);\n                if (!--map[num]) {\n                    map.erase(num);\n                }\n            }\n        }\n        return res;\n    }\n};\n```
[]