{x}
blog image

Find Subsequence of Length K With the Largest Sum

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.

 

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
  • -105 <= nums[i] <= 105
  • 1 <= k <= nums.length

Solution Explanation: Finding the Largest Sum Subsequence of Length K

The problem asks to find a subsequence of length k from a given integer array nums that has the largest possible sum. The solution uses a sorting-based approach for efficiency.

Approach:

  1. Index Array: We create an auxiliary array idx to store the indices of the original nums array. This allows us to sort based on the values in nums while preserving the original indices.

  2. Sorting: We sort the idx array using a custom comparator. The comparator sorts the indices based on the values in nums in ascending order. This means the indices of the smallest elements in nums will come first in idx.

  3. Selecting Top K: After sorting, the last k elements of the idx array represent the indices of the k largest elements in nums. We extract these indices.

  4. Reordering (Optional): The selected indices might not be in their original order in nums. To maintain the original order within the subsequence, we sort these k indices in ascending order.

  5. Result: Finally, we create the result array by using the sorted indices to fetch the corresponding elements from the original nums array.

Time Complexity Analysis:

  • Sorting the idx array takes O(n log n) time, where n is the length of nums.
  • Selecting the last k indices takes O(k) time, which is dominated by the sorting time.
  • Sorting the k selected indices takes O(k log k) time. Since k ≤ n, this is also dominated by the initial sorting.
  • Extracting the elements from nums based on the indices takes O(k) time.

Therefore, the overall time complexity is O(n log n), dominated by the initial sorting step.

Space Complexity Analysis:

  • The idx array uses O(n) space.
  • The auxiliary space used for sorting might vary based on the sorting algorithm used, but it's generally considered O(log n) or O(n) in the worst case for comparison-based sorting algorithms.
  • The result array uses O(k) space.

Hence, the overall space complexity is O(n) in the worst case.

Code Examples:

The provided code examples in Python, Java, Go, and TypeScript all implement this approach. They differ slightly in syntax and how they handle the sorting and index manipulation, but the core algorithm remains the same. Each example is annotated to aid understanding.

Note: The Integer[] in the Java example allows for using a custom comparator for sorting based on the values in the nums array. Other languages implicitly or explicitly support similar approaches. The Go example uses sort.Slice to achieve efficient sorting with a custom comparison function. The TypeScript version cleverly uses slice and map for conciseness.