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
15
16
class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        int n = nums.length;
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; ++i) {
            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
func maxSubsequence(nums []int, k int) []int {
    n := len(nums)
    idx := make([]int, n)
    for i := range idx {
        idx[i] = i
    }
    sort.Slice(idx, func(i, j int) bool { return nums[idx[i]] < nums[idx[j]] })
    sort.Ints(idx[n-k:])
    ans := make([]int, k)
    for i := n - k; i < n; i++ {
        ans[i-(n-k)] = nums[idx[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]);
}

Comments