Skip to content

2099. Find Subsequence of Length K With the Largest Sum

Description

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

Solutions

Solution 1: Sorting

First, we create an index array \(\textit{idx}\), where each element is an index of the array \(\textit{nums}\). Then, we sort the index array \(\textit{idx}\) based on the values in \(\textit{nums}\), with the sorting rule being \(\textit{nums}[i] < \textit{nums}[j]\), where \(i\) and \(j\) are two indices in the index array \(\textit{idx}\).

After sorting, we take the last \(k\) elements of the index array \(\textit{idx}\). These \(k\) elements correspond to the largest \(k\) elements in the array \(\textit{nums}\). Then, we sort these \(k\) indices to get the order of the largest \(k\) elements in the array \(\textit{nums}\).

The time complexity is \(O(n \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of the array.

1
2
3
4
class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        idx = sorted(range(len(nums)), key=lambda i: nums[i])[-k:]
        return [nums[i] for i in sorted(idx)]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        int n = nums.length;
        Integer[] idx = new Integer[n];
        Arrays.setAll(idx, i -> i);
        Arrays.sort(idx, (i, j) -> nums[i] - nums[j]);
        Arrays.sort(idx, n - k, n);
        int[] ans = new int[k];
        for (int i = n - k; i < n; ++i) {
            ans[i - (n - k)] = nums[idx[i]];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <ranges>

class Solution {
public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> idx(n);
        ranges::iota(idx, 0);
        ranges::sort(idx, [&](int i, int j) { return nums[i] < nums[j]; });
        ranges::sort(idx | views::drop(n - k));
        vector<int> ans(k);
        for (int i = n - k; i < n; ++i) {
            ans[i - (n - k)] = nums[idx[i]];
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func maxSubsequence(nums []int, k int) []int {
    idx := slices.Clone(make([]int, len(nums)))
    for i := range idx {
        idx[i] = i
    }
    slices.SortFunc(idx, func(i, j int) int { return nums[i] - nums[j] })
    slices.Sort(idx[len(idx)-k:])
    ans := make([]int, k)
    for i := range ans {
        ans[i] = nums[idx[len(idx)-k+i]]
    }
    return ans
}

1
2
3
4
5
6
7
8
9
function maxSubsequence(nums: number[], k: number): number[] {
    const n = nums.length;
    const idx: number[] = Array.from({ length: n }, (_, i) => i);
    idx.sort((i, j) => nums[i] - nums[j]);
    return idx
        .slice(n - k)
        .sort((i, j) => i - j)
        .map(i => nums[i]);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn max_subsequence(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let n = nums.len();
        let k = k as usize;
        let mut idx: Vec<usize> = (0..n).collect();

        idx.sort_by_key(|&i| nums[i]);
        idx[n - k..].sort();

        let mut ans = Vec::with_capacity(k);
        for i in n - k..n {
            ans.push(nums[idx[i]]);
        }

        ans
    }
}

Comments