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.lengthclass Solution {
public int[] maxSubsequence(int[] nums, int k) {
Queue<int[]> pq1 = new PriorityQueue<>((a, b) -> b[0] - a[0]);
Queue<int[]> pq2 = new PriorityQueue<>((a, b) -> a[1] - b[1]);
for (int i = 0; i < nums.length; i++)
pq1.offer(new int[] { nums[i], i });
for (int i = 0; i < k; i++)
pq2.offer(pq1.poll());
int[] ans = new int[k];
int i = 0;
while (!pq2.isEmpty())
ans[i++] = pq2.poll()[0];
return ans;
}
}class Solution {
public int[] maxSubsequence(int[] nums, int k) {
int n = nums.length;
int[][] store = new int[n][2];
for (int i = 0; i < n; i++)
store[i] = new int[] { nums[i], i };
Arrays.sort(store, (a, b) -> b[0] - a[0]);
Arrays.sort(store, 0, k, (a, b) -> a[1] - b[1]);
int[] ans = new int[k];
for (int i = 0; i < k; i++)
ans[i] = store[i][0];
return ans;
}
}class Solution {
public int[] maxSubsequence(int[] nums, int k) {
Queue<int[]> pq1 = new PriorityQueue<>((a, b) -> b[0] - a[0]);
Queue<int[]> pq2 = new PriorityQueue<>((a, b) -> a[1] - b[1]);
for (int i = 0; i < nums.length; i++)
pq1.offer(new int[] { nums[i], i });
for (int i = 0; i < k; i++)
pq2.offer(pq1.poll());
int[] ans = new int[k];
int i = 0;
while (!pq2.isEmpty())
ans[i++] = pq2.poll()[0];
return ans;
}
}