✅ [Python/C++] From O(nlogn) to O(n) || One-liner || 100% Faster || Detailed Explanation
The subsequence of length k with the largest sum are composed of the largest k numbers in nums.\n \'sorted(nums, reverse=True)[:k]\' can find the  largest k num
* The subsequence of length k with the largest sum are composed of the largest k numbers in nums.\n* \'sorted(nums, reverse=True)[:k]\' can find the  largest k numbers in num, but destroy their original order.\n* We can traverse the list again and reconstruct the original order of max_k in the list.\n\n**Python 100% Faster**\n```\nclass Solution(object):\n    def maxSubsequence(self, nums, k):\n        ret, max_k = [], sorted(nums, reverse=True)[:k]\n        for num in nums:\n            if num in max_k:\n                ret.append(num)\n                max_k.remove(num)\n                if len(max_k) == 0:\n                    return ret\n```\n**An alternative python solution, maybe a little more pythonic!**\n```\nclass Solution(object):\n    def maxSubsequence(self, nums, k):\n        # Build a two-keyword(index, num) list and sort by num in reverse order and intercept the top k\n        nums_with_idx_topk = sorted(enumerate(nums), reverse=True, key=lambda elem: elem[1])[:k]\n        nums_with_idx_topk = sorted(nums_with_idx_topk)  # Sort by index in order\n        return [num for i, num in nums_with_idx_topk]\n```\n**Python, One-liner, 100% Faster, Upvote!**\n```\nclass Solution(object):\n    def maxSubsequence(self, nums, k):\n        return [n for i, n in sorted(sorted(enumerate(nums), key=lambda e: -e[1])[:k])]\n```\n**Further More O(n), Using Quick Select**\n* The average Time Complexity of Quick Select is O(n), while the worst-case performance is O(n<sup>2</sup>).\n\t* Note that it is very important to choose the split point randomly.\n* Learn more about quick select algorithm: https://en.wikipedia.org/wiki/Quickselect\n\n```\nclass Solution(object):\n    def maxSubsequence(self, nums, k):\n        def findKthLargest(nums, k):\n            pivot = random.choice(nums)\n            less = [num for num in nums if num < pivot]\n            equal = [num for num in nums if num == pivot]\n            greater = [num for num in nums if num > pivot]\n\n            if len(greater) >= k:\n                return findKthLargest(greater, k)\n            elif len(greater) + len(equal) < k:\n                return findKthLargest(less, k - len(greater) - len(equal))\n            else:\n                return pivot, k - len(greater)\n\n        kth_largest, kth_largest_equal = findKthLargest(nums, k)\n        ans = []\n        for num in nums:\n            if num > kth_largest:\n                ans.append(num)\n            elif num == kth_largest and kth_largest_equal:\n                ans.append(num)\n                kth_largest_equal -= 1\n        return ans\n```\n**If you hava any question, feel free to ask. If you like the solution or the explaination, Please UPVOTE!**\n\n**C++ 53% Faster**\n```\nclass Solution {\npublic:\n    vector<int> maxSubsequence(vector<int>& nums, int k) {\n        vector<int> max_k(nums);\n        vector<int> ret;\n        sort(max_k.rbegin(), max_k.rend());\n        for (int i = 0; i < size(nums); i ++) {\n            for (int j = 0; j < k; j ++) {\n                if (nums[i] == max_k[j]) {\n                    ret.push_back(nums[i]);\n                    nums[i] = -1000000;\n                    max_k[j] = 1000000;\n                    if (size(ret) == k) return ret;\n                }\n            }\n        }\n        return ret;\n    }\n};\n```\n**If you hava any question, feel free to ask. If you like the solution or the explaination, Please UPVOTE!**
['Python', 'C++']