Problem Description

You are given an array of integers nums and an integer k. Your task is to find a subsequence from nums that has exactly k elements and the maximum possible sum.

A subsequence is a sequence that can be obtained from the original array by removing some (or no) elements while maintaining the relative order of the remaining elements. For example, [1, 3, 5] is a subsequence of [1, 2, 3, 4, 5].

The key requirements are:

• The subsequence must have exactly k elements
• The subsequence must have the largest possible sum among all subsequences of length k
• The elements in the subsequence must maintain their original relative order from nums
• You need to return the actual subsequence (not just its sum) as an array of length k

For example, if nums = [2, 1, 3, 3] and k = 2, you should return [3, 3] because this subsequence of length 2 has the maximum sum of 6. Note that the order is preserved - both 3's appear in the same order as they did in the original array.

The solution works by first identifying which k elements from nums are the largest (using sorting with indices), then arranging these selected elements in their original order to form the final subsequence.

Intuition

To find the subsequence with the maximum sum, we need to select the k largest elements from the array. This is because including any smaller element instead of a larger one would decrease our total sum.

However, there's a catch - we can't just take the k largest values and return them in descending order. We need to maintain the original relative order of these elements as they appeared in nums. This is what makes it a subsequence problem rather than just a sorting problem.

The key insight is to work with indices rather than values directly. If we track the original positions of elements while identifying the largest ones, we can then reconstruct them in their original order.

Here's the thought process:

1. We need to identify which elements are the k largest - but we also need to remember where they came from in the original array
2. Instead of sorting the values directly, we sort the indices [0, 1, 2, ..., n-1] based on their corresponding values in nums
3. After sorting by value, the last k indices in our sorted index array point to the k largest elements
4. But these indices might be in any order - for example, if we selected indices [5, 2, 7], the elements at these positions need to be returned in the order [2, 5, 7] to maintain the original sequence
5. So we sort these selected indices to restore the original ordering, then extract the corresponding values

This approach elegantly solves both requirements: selecting the maximum sum elements while preserving their original order in the array.

Learn more about Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a sorting-based approach with index manipulation to solve the problem efficiently.

Step 1: Create and Sort Index Array

First, we create an index array using range(len(nums)), which gives us [0, 1, 2, ..., n-1]. Then we sort these indices based on their corresponding values in nums:

idx = sorted(range(len(nums)), key=lambda i: nums[i])[-k:]

The key=lambda i: nums[i] tells Python to sort the indices based on the values at those positions in nums. For example, if nums = [2, 1, 3, 3], the indices [0, 1, 2, 3] would be sorted as [1, 0, 2, 3] because:

• nums[1] = 1 (smallest)
• nums[0] = 2
• nums[2] = 3
• nums[3] = 3

Step 2: Select Top k Indices

After sorting, we take the last k elements using [-k:]. These are the indices of the k largest elements in nums. Continuing our example with k = 2, we'd get [2, 3], which are the indices of the two largest values.

Step 3: Restore Original Order

The selected indices might not be in ascending order. To maintain the subsequence property, we need to sort these indices:

sorted(idx)

This ensures that when we extract the values, they appear in the same relative order as in the original array.

Step 4: Build Result Array

Finally, we use list comprehension to extract the actual values:

return [nums[i] for i in sorted(idx)]

This creates a new array containing the values at the selected and sorted indices.

Time Complexity: O(n log n) due to sorting the entire index array
Space Complexity: O(n) for storing the index array

The beauty of this solution is that it handles both requirements (maximum sum and order preservation) through clever index manipulation rather than complex logic.

Example Walkthrough

Let's walk through the solution with nums = [10, 20, 7, 15, 30] and k = 3.

Step 1: Create and Sort Index Array

We start with indices [0, 1, 2, 3, 4] representing positions in nums.

Now we sort these indices based on their values in nums:

• Index 2 → value 7 (smallest)
• Index 0 → value 10
• Index 3 → value 15
• Index 1 → value 20
• Index 4 → value 30 (largest)

Sorted indices by value: [2, 0, 3, 1, 4]

Step 2: Select Top k Indices

We need k = 3 elements with maximum sum, so we take the last 3 indices from our sorted array: idx = [3, 1, 4]

These correspond to values 15, 20, and 30 - the three largest elements.

Step 3: Restore Original Order

The indices [3, 1, 4] are not in ascending order. To maintain the subsequence property, we sort them: sorted(idx) = [1, 3, 4]

This ensures the elements appear in their original relative order.

Step 4: Build Result Array

Extract values at these sorted indices:

• nums[1] = 20
• nums[3] = 15
• nums[4] = 30

Result: [20, 15, 30]

This subsequence has sum = 65 (maximum possible) and maintains the original order from nums.

Solution Implementation

Time and Space Complexity

The time complexity is O(n log n), where n is the length of the input array nums. This is dominated by the sorting operation sorted(range(len(nums)), key=lambda i: nums[i]), which sorts all indices based on their corresponding values in nums. Even though we only select the last k elements after sorting, we still need to sort all n indices first. The second sorting operation sorted(idx) takes O(k log k) time, but since k ≤ n, this is absorbed by the overall O(n log n) complexity.

The space complexity is O(n). The range(len(nums)) creates a list of n indices, and the sorted() function creates a new sorted list of size n. Although the reference answer states O(log n) space complexity (likely referring to the auxiliary space used by the sorting algorithm itself), the actual space complexity of this implementation is O(n) due to the explicit creation of the index list. The final list comprehension creates an output list of size k, but this is typically not counted as part of the space complexity since it's the required output.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to Sort Indices Before Building Result

A common mistake is directly using the selected indices without sorting them first:

# WRONG - This doesn't preserve the original order
def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
    idx = sorted(range(len(nums)), key=lambda i: nums[i])[-k:]
    return [nums[i] for i in idx]  # Missing sorted() here!

Why it's wrong: After selecting the k largest indices, they are ordered by value, not by position. For example, with nums = [2, 1, 3, 3] and k = 2, idx would be [2, 3], but if the largest element was at index 0, we might get [3, 0], producing [3, 2] instead of [2, 3].

Solution: Always sort the indices before extracting values:

return [nums[i] for i in sorted(idx)]

Pitfall 2: Using Value-Based Sorting Instead of Index-Based

Another mistake is trying to sort values directly and losing track of positions:

# WRONG - This loses positional information
def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
    sorted_nums = sorted(nums)[-k:]  # Gets k largest values
    # But now we can't reconstruct the original order!
    return sorted_nums

Why it's wrong: Once you sort the values directly, you lose the connection to their original positions. You can't determine which occurrence of duplicate values to use or how to restore the original order.

Solution: Always work with indices to maintain the position-value relationship:

idx = sorted(range(len(nums)), key=lambda i: nums[i])[-k:]

Pitfall 3: Misunderstanding Subsequence vs Subarray

Some might try to find a contiguous subarray instead of a subsequence:

# WRONG - Looking for contiguous elements
def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
    max_sum = float('-inf')
    result = []
    for i in range(len(nums) - k + 1):
        current = nums[i:i+k]
        if sum(current) > max_sum:
            max_sum = sum(current)
            result = current
    return result

Why it's wrong: A subsequence can skip elements while maintaining order. The problem asks for any k elements (not necessarily consecutive) that give the maximum sum.

Solution: Use the index-based approach that can select non-contiguous elements while preserving their relative order.