2099. Find Subsequence of Length K With the Largest Sum-找到和最大的长度为 K 的子序列

给你一个整数数组nums和一个整数k。你需要找到nums中长度为k的子序列，且这个子序列的和最大。

请你返回任意一个长度为k的整数子序列。

子序列定义为从一个数组里删除一些元素后，不改变剩下元素的顺序得到的数组。

示例 1：

输入：nums = [2,1,3,3], k = 2
输出：[3,3]
解释：
子序列有最大和：3 + 3 = 6 。

示例 2：

输入：nums = [-1,-2,3,4], k = 3
输出：[-1,3,4]
解释：
子序列有最大和：-1 + 3 + 4 = 6 。

示例 3：

输入：nums = [3,4,3,3], k = 2
输出：[3,4]
解释：
子序列有最大和：3 + 4 = 7 。
另一个可行的子序列为 [4, 3] 。

提示：

• 1 <= nums.length <= 1000
• -10^5 <= nums[i] <= 10^5
• 1 <= k <= nums.length

Python:

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        temp = sorted(nums)
        adic = dict()
        for item in temp[-k:]:
            if item not in adic.keys():
                adic[item] = 1
            else:
                adic[item] += 1
        alis = []
        for item in nums:
            if item in adic.keys() and adic[item] > 0:
                alis.append(item)
                adic[item] -= 1
        return alis

Java:

class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        int[] temp = new int[nums.length];
        int[] result = new int[k];
        temp = nums.clone();
        Arrays.sort(temp);
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = temp.length-1; i > temp.length-1-k; i--)
        {
            if(!map.containsKey(temp[i]))
                map.put(temp[i], 1);
            else
                map.compute(temp[i], (key, v) -> v+=1);
        }
        int i = 0;
        for(int num: nums)
        {
            if(map.containsKey(num) && map.get(num) > 0)
            {
                result[i] = num;
                map.compute(num, (key, v) -> v-=1);
                i++;
            }
        }
        return result;
    }
}