Problem

You are given an integer array nums and an integer k. You want to find a subsequence of nums of length k that has the largest sum.

Return any such subsequence as an integer array of length k.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Testcases

Example 1:

Input: nums = [2,1,3,3], k = 2
Output: [3,3]
Explanation:
The subsequence has the largest sum of 3 + 3 = 6.
Example 2:

Input: nums = [-1,-2,3,4], k = 3
Output: [-1,3,4]
Explanation:
The subsequence has the largest sum of -1 + 3 + 4 = 6.
Example 3:

Input: nums = [3,4,3,3], k = 2
Output: [3,4]
Explanation:
The subsequence has the largest sum of 3 + 4 = 7.
Another possible subsequence is [4, 3].

Constraints:

1 <= nums.length <= 1000
-10^5 <= nums[i] <= 10^5
1 <= k <= nums.length

Intuition

To achieve the largest possible sum of a subsequence of length k, it makes sense to select the k largest elements from the array. However, since a subsequence must preserve the original order of elements, we can't simply sort and pick — we must track both the value and the original index.

Approach

Use a min-heap (priority queue) to maintain the top k largest elements. Each element in the heap is a pair of [value, index].

When the heap size exceeds k, remove the smallest element. This ensures the heap always contains the k largest elements.

Use a TreeMap to store the k elements with their original indices as keys. This automatically sorts them by index to preserve their relative order.

Build the result array by traversing the TreeMap in key order.

Time Complexity

O(n log k) — inserting into the heap for n elements with max size k

O(k log k) — for TreeMap insertion and sorting by index

O(k) — to construct the result array
Total: O(n log k + k log k)

Space Complexity

O(k) — for the heap and the TreeMap

Code

class Solution { public int[] maxSubsequence(int[] nums, int k) { if (nums == null || k < 0) { return new int []{}; } int length = nums.length; int [] result = new int [k]; PriorityQueue<int[]> minHeap = new PriorityQueue<>((p1, p2) -> Integer.compare(p1[0], p2[0])); TreeMap<Integer, Integer> kIndexNumber = new TreeMap<>(); for (int index = 0; index < length; index++) { minHeap.offer(new int []{nums[index], index}); if (minHeap.size() > k) { minHeap.poll(); } } int resultIndex = 0; while (!minHeap.isEmpty()) { int [] top = minHeap.poll(); kIndexNumber.put(top[1], top[0]); } for (Integer key : kIndexNumber.keySet()) { result[resultIndex++] = kIndexNumber.get(key); } return result; } }