Find Subsequence of Length K With the Largest Sum
Problem
Given an array nums and integer k, find any subsequence of length k that has the largest possible sum. Return that subsequence (in any order that preserves a valid subsequence).
nums = [2,1,3,3], k = 2[3,3]def max_subsequence(nums, k):
idx = sorted(range(len(nums)), key=lambda i: nums[i], reverse=True)
chosen = sorted(idx[:k])
return [nums[i] for i in chosen]function maxSubsequence(nums, k) {
const idx = nums.map((v, i) => i);
idx.sort((a, b) => nums[b] - nums[a]);
const chosen = idx.slice(0, k).sort((a, b) => a - b);
return chosen.map(i => nums[i]);
}class Solution {
public int[] maxSubsequence(int[] nums, int k) {
Integer[] idx = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> nums[b] - nums[a]);
int[] chosen = new int[k];
for (int i = 0; i < k; i++) chosen[i] = idx[i];
Arrays.sort(chosen);
int[] res = new int[k];
for (int i = 0; i < k; i++) res[i] = nums[chosen[i]];
return res;
}
}vector<int> maxSubsequence(vector<int>& nums, int k) {
vector<int> idx(nums.size());
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int a, int b){ return nums[a] > nums[b]; });
vector<int> chosen(idx.begin(), idx.begin() + k);
sort(chosen.begin(), chosen.end());
vector<int> res;
for (int i : chosen) res.push_back(nums[i]);
return res;
}Explanation
To maximize the sum of a length-k subsequence we obviously want the k largest values — there is no benefit to ever including a smaller element in place of a larger one.
The subtlety is duplicates: if we sorted the values alone we might lose track of which positions to keep. So we sort the indices by their value descending and take the first k of them. This picks exactly k positions, breaking ties by index rather than dropping a needed duplicate.
A subsequence must keep elements in their original relative order, so we re-sort the chosen indices ascending before reading off their values.
Sorting dominates the cost at O(n log n); building the result is linear. The extra index array is O(n) space.
Example: [2,1,3,3], k = 2. By value the index order is [2,3,0,1] (values 3,3,2,1). The top two indices are {2,3}; sorted ascending they read off [3,3] with sum 6.