Choose a subsequence of length whose elements have the maximum possible sum, while keeping the selected numbers in their original relative order.
Problem
Given an integer array nums and an integer k, return a subsequence of nums of length k such that:
- The subsequence has the largest possible sum among all subsequences of length
k. - If multiple subsequences have the same sum, any valid answer is acceptable.
- The relative order of the chosen elements must be the same as in the original array.
A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements.
Notes
- You do not need to return the sum itself.
- The returned sequence must contain exactly
kelements. - If there are duplicate values, selecting the correct occurrences matters because order must be preserved.
Input Format
- A single integer array
nums. - A single integer
k.
You may assume the array and k are provided in the usual coding-interview format.
Output Format
- Return any subsequence of
numswith lengthkand maximum possible sum, preserving original order.
Constraints
- Elements of
numsmay be negative, zero, or positive - Use 64-bit arithmetic if needed to avoid overflow
Example 1
Input
nums = [2, 1, 3, 3], k = 2
Output
[3, 3]
Explanation
The maximum sum subsequence of length 2 uses the two largest values, which are both 3. Their original order is preserved.
Example 2
Input
nums = [-1, -2, 3, 4], k = 2
Output
[3, 4]
Explanation
The best choice is the subsequence with sum 7. The order is already valid in the original array.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.