Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The greatest possible sum uses the k largest values, but a subsequence must preserve their original relative order. Separate selecting the values from arranging the selected occurrences back into index order.

Approach

Pair every value with its original index and sort those pairs by value. Keep the largest k, then sort the selected pairs by original index and return their values. Equal-valued boundary choices may be resolved by the implementation's tie order because they give the same maximum sum. The Python version replaces entries in its input list with indexed pairs while preparing the selection; the returned answer is a separate value list.

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)

        for i in range(n): nums[i] = [nums[i], i]

        nums.sort()
        nums = nums[-k:]
        nums.sort(key = lambda x: x[1])

        res = []
        for i in range(k): res.append(nums[i][0])

        return res

Complexity analysis

Let n = nums.length. Time: O(n log n) for the value sort and the final index-order sort. Auxiliary space: O(n) for indexed pairs and sorting; the returned subsequence uses O(k) space.