Choose a Maximum-Sum Ordered Subsequence

### Problem Return a subsequence of `nums` containing exactly `k` entries with the greatest possible sum. A subsequence keeps the selected entries in their original relative order; it need not be contiguous. If several subsequences have the maximum sum, return any of them. ```cpp class Solution { public: vector<int> maxSubsequence(vector<int>& nums, int k); }; ``` ### Examples **Example 1:** ```text nums = [5,1,4,3], k = 2 Output: [5,4] Explanation: The two greatest entries sum to 9 and occur in this order. ``` **Example 2:** ```text nums = [2,3,2], k = 2 Output: [2,3] Explanation: Sum 5 is optimal; [3,2] is another permitted answer. ``` ### Constraints - `1 <= nums.length <= 1000`; `1 <= k <= nums.length`. - `-10^5 <= nums[i] <= 10^5`. ### Clarifying Questions The returned entries must occur in input order. Ties may permit different original positions and different equally optimal subsequences. ```hint Inspect the structure How can original indices restore subsequence order after selecting by value? ``` ### What a Strong Answer Covers - Select exactly k entries and justify that their sum is maximal, including for all-negative input. - Preserve original relative order in the returned subsequence. - Allow every source-valid optimum when equal values permit different choices. ### Follow-up Questions Could you improve the running time while preserving the subsequence requirement?