Split point - O(n)
Somehow, this was the hardest question for me. I misunderstood the description - twice!\n \n> Update: inspired by qeetcode, here is an O(n) solution (in average
Somehow, this was the hardest question for me. I misunderstood the description - twice!\n \n> Update: inspired by [qeetcode](https://leetcode.com/qeetcode/), here is an O(n) solution (in average).\n \nWe use quick select to determine the k-largest element. The idea is that all elements bigger than k-largest will be in the result array.\n \nWhat about the k-largest element itself? Right, duplicates could stir some trouble. So, we count how many times (`cnt`) k-largest elements appear within `k` numbers.\n\n**C++**\n```cpp\nvector<int> maxSubsequence(vector<int>& nums, int k) {\n    if (k == nums.size())\n        return nums;\n    vector<int> v(begin(nums), end(nums)), res;\n    nth_element(begin(v), begin(v) + k - 1, end(v), greater<int>());\n    int cnt = count(begin(v), begin(v) + k, v[k - 1]);\n    for (int i = 0; i < nums.size(); ++i)\n        if (nums[i] > v[k - 1] || (nums[i] == v[k - 1] && --cnt >= 0))\n            res.push_back(nums[i]);\n    return res;\n}\n```\n\n#### O(n + k log k)\nJust for the reference - the original solution. Here we sort k numbers instead of working off the split point.\n\n**C++**\n```cpp\nvector<int> maxSubsequence(vector<int>& nums, int k) {\n    vector<pair<int, int>> v;\n    for (int i = 0; i < nums.size(); ++i)\n        v.push_back({nums[i], i});\n    nth_element(begin(v), begin(v) + k, end(v), greater<pair<int, int>>());\n    sort(begin(v), begin(v) + k, [](const auto &a, const auto &b){ return a.second < b.second; });\n    vector<int> res;\n    transform(begin(v), begin(v) + k, back_inserter(res), [](const auto &p){ return p.first; });\n    return res;\n}\n```
[]