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

Thinking

Maximum sum with original order means the \(k\) largest values, then sorted by index. \(n \le 1000\), so sort indices by value.

Keep the last \(k\) indices and emit nums in increasing index order.

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