LeetCode 2099. Find Subsequence of Length K With the Largest Sum Solution in Java, C++, Python & More | Explanation + Code

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 idx, where each element is an index of the array nums. Then, we sort the index array idx based on the values in nums, with the sorting rule being nums[i] < nums[j], where i and j are two indices in the index array idx.

After sorting, we take the last k elements of the index array idx. These k elements correspond to the largest k elements in the array nums. Then, we sort these k indices to get the order of the largest k elements in the array 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.

PythonJavaC++GoTypeScriptRust

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)](code-box)

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; } }(code-box)

#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; } };(code-box)

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 }(code-box)

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]); }(code-box)

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 } }(code-box)