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.

Examples

Example 1

1
2
3
4

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

Example 2

1
2
3
4

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

1
2
3
4
5

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

Solution

Method 1 – Heap & Index Tracking

Intuition

To get the largest sum subsequence of length k, we need the k largest elements from nums, but we must preserve their original order. By selecting the k largest elements (with their indices), sorting those indices, and then extracting the values in order, we ensure both maximal sum and correct subsequence order.

Approach

  1. Pair each element in nums with its index.
  2. Sort these pairs by value in descending order.
  3. Select the first k pairs (the largest k elements).
  4. Extract their indices and sort them to maintain the original order.
  5. Build the answer by picking elements from nums at these sorted indices.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
  vector<int> maxSubsequence(vector<int>& nums, int k) {
    vector<pair<int, int>> v;
    for (int i = 0; i < nums.size(); ++i)
      v.push_back({nums[i], i});
    sort(v.rbegin(), v.rend());
    vector<int> idx;
    for (int i = 0; i < k; ++i)
      idx.push_back(v[i].second);
    sort(idx.begin(), idx.end());
    vector<int> ans;
    for (int i : idx)
      ans.push_back(nums[i]);
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func maxSubsequence(nums []int, k int) []int {
  type pair struct{ val, idx int }
  v := make([]pair, len(nums))
  for i, num := range nums {
    v[i] = pair{num, i}
  }
  sort.Slice(v, func(i, j int) bool {
    return v[i].val > v[j].val
  })
  idx := make([]int, k)
  for i := 0; i < k; i++ {
    idx[i] = v[i].idx
  }
  sort.Ints(idx)
  ans := make([]int, k)
  for i, id := range idx {
    ans[i] = nums[id]
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
  public int[] maxSubsequence(int[] nums, int k) {
    int n = nums.length;
    int[][] v = new int[n][2];
    for (int i = 0; i < n; i++) {
      v[i][0] = nums[i];
      v[i][1] = i;
    }
    Arrays.sort(v, (a, b) -> b[0] - a[0]);
    int[] idx = new int[k];
    for (int i = 0; i < k; i++) {
      idx[i] = v[i][1];
    }
    Arrays.sort(idx);
    int[] ans = new int[k];
    for (int i = 0; i < k; i++) {
      ans[i] = nums[idx[i]];
    }
    return ans;
  }
}
1
2
3
4
5
6
7
8

class Solution {
  fun maxSubsequence(nums: IntArray, k: Int): IntArray {
    val v = nums.mapIndexed { i, num -> Pair(num, i) }
      .sortedByDescending { it.first }
    val idx = v.take(k).map { it.second }.sorted()
    return idx.map { nums[it] }.toIntArray()
  }
}
1
2
3
4
5

class Solution:
  def maxSubsequence(self, nums: list[int], k: int) -> list[int]:
    v = sorted([(num, i) for i, num in enumerate(nums)], reverse=True)
    idx = sorted([i for _, i in v[:k]])
    return [nums[i] for i in idx]
1
2
3
4
5
6
7
8
9

impl Solution {
  pub fn max_subsequence(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let mut v: Vec<(i32, usize)> = nums.iter().cloned().zip(0..).collect();
    v.sort_by(|a, b| b.0.cmp(&a.0));
    let mut idx: Vec<usize> = v.iter().take(k as usize).map(|&(_, i)| i).collect();
    idx.sort();
    idx.iter().map(|&i| nums[i]).collect()
  }
}

Complexity

  • ⏰ Time complexity: O(n log n) (for sorting)
  • 🧺 Space complexity: O(n) (for storing pairs and indices)