Find subsequence of length k with the largest sum

Array Hash Table Sorting Heap (Priority Queue)

57.4% acceptance

Feb 25, 2026

1753

184

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_subsequence(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let k = k as usize;
    // Get indices sorted by descending value, take first k
    let mut indices: Vec<usize> = (0..nums.len()).collect();
    indices.sort_unstable_by(|&a, &b| nums[b].cmp(&nums[a]));
    let mut selected: Vec<usize> = indices[..k].to_vec();
    // Sort by original index to preserve order
    selected.sort_unstable();
    selected.iter().map(|&i| nums[i]).collect()
  }
}