Problem Statement

Given an integer array nums and a positive integer k, return any subsequence of nums of length k, which has the largest sum.

A subsequence maintains the original order of array elements but may exclude some, without reordering the remaining ones.

Examples

• Example 1:

  • Input: nums = [5, -2, 3, 8], k = 2
  • Expected Output: [5, 8]
  • Justification: The subsequence [5, 8] gives the largest sum of 13, which is the maximum sum we can obtain from any subsequence of length 2.

• Example 2:

  • Input: nums = [-1, -2, -3, -4], k = 3
  • Expected Output: [-1, -2, -3]
  • Justification: Although all numbers are negative, the subsequence [-1, -2, -3] has the least negative sum, making it the largest sum (-6) for a length of 3.

• Example 3:

  • Input: nums = [4, 3, 1, 2, 5], k = 4
  • Expected Output: [4, 3, 2, 5]
  • Justification: The subsequence [4, 3, 2, 5] sums up to 14, which is the highest possible sum for any subsequence of length 4 in the given array.

Try it yourself

Try solving this question here: