[LeetCode 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
• -10^5 <= nums[i] <= 10^5
• 1 <= k <= nums.length

Hint

---

Hint 1

  From a greedy perspective, what k elements should you pick?
	

Hint 2

  Could you sort the array while maintaining the index?
	

Code

---

내 제출

---

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;
    }
}

Runtime	Memory
9 ms	44.7 MB

다른 풀이

---

class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        int n = nums.length;
        int[][] vals = new int[n][2];
        for(int i=0; i<n; i++){
            vals[i][0] = i;
            vals[i][1] = nums[i];
        }
        Arrays.sort(vals,(x1,x2) -> Integer.compare(x2[1],x1[1]));
        Arrays.sort(vals,0,k,(x1,x2) -> Integer.compare(x1[0],x2[0]));

        int[] res = new int[k];
        for(int i=0; i<k; i++){
            res[i] = vals[i][1];
        }
        return res;
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/2000-2099/2099.Find%20Subsequence%20of%20Length%20K%20With%20the%20Largest%20Sum/Solution.java