Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2099.html
2099. Find Subsequence of Length K With the Largest Sum (Easy)
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] <= 1051 <= k <= nums.length
Similar Questions:
- Kth Largest Element in an Array (Medium)
- Maximize Sum Of Array After K Negations (Easy)
- Sort Integers by The Number of 1 Bits (Easy)
Solution 1. Sorting
-
// OJ: https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/ // Time: O(NlogN) // Space: O(N) class Solution { public: vector<int> maxSubsequence(vector<int>& A, int k) { vector<int> id(A.size()); iota(begin(id), end(id), 0); // Index array 0, 1, 2, ... sort(begin(id), end(id), [&](int a, int b) { return A[a] > A[b]; }); // Sort the indexes in descending order of their corresponding values in `A` id.resize(k); // Only keep the first `k` indexes with the greatest `A` values sort(begin(id), end(id)); // Sort indexes in ascending order vector<int> ans; for (int i : id) ans.push_back(A[i]); return ans; } }; -
class Solution: def maxSubsequence(self, nums: List[int], k: int) -> List[int]: idx = list(range(len(nums))) idx.sort(key=lambda i: nums[i]) return [nums[i] for i in sorted(idx[-k:])] ############ # 2099. Find Subsequence of Length K With the Largest Sum # https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/ class Solution: def maxSubsequence(self, nums: List[int], k: int) -> List[int]: res = set(list(range(k))) heap = [(x, i) for i, x in enumerate(nums[:k])] heapq.heapify(heap) for i, x in enumerate(nums[k:], k): res.add(i) value, index = heapq.heappushpop(heap, (x, i)) res.remove(index) return [nums[i] for i in sorted(list(res))] -
class Solution { public int[] maxSubsequence(int[] nums, int k) { int[] ans = new int[k]; List<Integer> idx = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n; ++i) { idx.add(i); } idx.sort(Comparator.comparingInt(i -> - nums[i])); int[] t = new int[k]; for (int i = 0; i < k; ++i) { t[i] = idx.get(i); } Arrays.sort(t); for (int i = 0; i < k; ++i) { ans[i] = nums[t[i]]; } return ans; } } -
func maxSubsequence(nums []int, k int) []int { idx := make([]int, len(nums)) 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[:k]) ans := make([]int, k) for i, j := range idx[:k] { ans[i] = nums[j] } return ans }
Solution 2. Quick Select
-
// OJ: https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/ // Time: O(N + KlogK) on average, O(N^2 + KlogK) in the worst case // Space: O(N) class Solution { public: vector<int> maxSubsequence(vector<int>& A, int k) { vector<int> id(A.size()); iota(begin(id), end(id), 0); nth_element(begin(id), begin(id) + k, end(id), [&](int a, int b) { return A[a] > A[b]; }); id.resize(k); sort(begin(id), end(id)); vector<int> ans; for (int i : id) ans.push_back(A[i]); return ans; } }; -
class Solution: def maxSubsequence(self, nums: List[int], k: int) -> List[int]: idx = list(range(len(nums))) idx.sort(key=lambda i: nums[i]) return [nums[i] for i in sorted(idx[-k:])] ############ # 2099. Find Subsequence of Length K With the Largest Sum # https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/ class Solution: def maxSubsequence(self, nums: List[int], k: int) -> List[int]: res = set(list(range(k))) heap = [(x, i) for i, x in enumerate(nums[:k])] heapq.heapify(heap) for i, x in enumerate(nums[k:], k): res.add(i) value, index = heapq.heappushpop(heap, (x, i)) res.remove(index) return [nums[i] for i in sorted(list(res))] -
class Solution { public int[] maxSubsequence(int[] nums, int k) { int[] ans = new int[k]; List<Integer> idx = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n; ++i) { idx.add(i); } idx.sort(Comparator.comparingInt(i -> - nums[i])); int[] t = new int[k]; for (int i = 0; i < k; ++i) { t[i] = idx.get(i); } Arrays.sort(t); for (int i = 0; i < k; ++i) { ans[i] = nums[t[i]]; } return ans; } } -
func maxSubsequence(nums []int, k int) []int { idx := make([]int, len(nums)) 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[:k]) ans := make([]int, k) for i, j := range idx[:k] { ans[i] = nums[j] } return ans }
Solution 3. Quick Select
-
// OJ: https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/ // Time: O(N) on average, O(N^2) in the worst case // Space: O(N) class Solution { public: vector<int> maxSubsequence(vector<int>& A, int k) { if (k == A.size()) return A; vector<int> v(begin(A), end(A)), ans; nth_element(begin(v), begin(v) + k - 1, end(v), greater<>()); int cnt = count(begin(v), begin(v) + k, v[k - 1]); for (int i = 0; i < A.size(); ++i) { if (A[i] > v[k - 1] || (A[i] == v[k - 1] && --cnt >= 0)) ans.push_back(A[i]); } return ans; } }; -
class Solution: def maxSubsequence(self, nums: List[int], k: int) -> List[int]: idx = list(range(len(nums))) idx.sort(key=lambda i: nums[i]) return [nums[i] for i in sorted(idx[-k:])] ############ # 2099. Find Subsequence of Length K With the Largest Sum # https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/ class Solution: def maxSubsequence(self, nums: List[int], k: int) -> List[int]: res = set(list(range(k))) heap = [(x, i) for i, x in enumerate(nums[:k])] heapq.heapify(heap) for i, x in enumerate(nums[k:], k): res.add(i) value, index = heapq.heappushpop(heap, (x, i)) res.remove(index) return [nums[i] for i in sorted(list(res))] -
class Solution { public int[] maxSubsequence(int[] nums, int k) { int[] ans = new int[k]; List<Integer> idx = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n; ++i) { idx.add(i); } idx.sort(Comparator.comparingInt(i -> - nums[i])); int[] t = new int[k]; for (int i = 0; i < k; ++i) { t[i] = idx.get(i); } Arrays.sort(t); for (int i = 0; i < k; ++i) { ans[i] = nums[t[i]]; } return ans; } } -
func maxSubsequence(nums []int, k int) []int { idx := make([]int, len(nums)) 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[:k]) ans := make([]int, k) for i, j := range idx[:k] { ans[i] = nums[j] } return ans }
Discuss
https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/discuss/1623427/C%2B%2B-Sorting-or-Quick-Select