2099.找到和最大的长度为 K 的子序列：自定义排序

【LetMeFly】2099.找到和最大的长度为 K 的子序列：自定义排序

力扣题目链接：https://leetcode.cn/problems/find-subsequence-of-length-k-with-the-largest-sum/

给你一个整数数组 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
• -105 <= nums[i] <= 105
• 1 <= k <= nums.length

Long Time No See.

解题方法：排序

使用一个“下标数组”idx，初始值$idx[i] = i$，然后对这个idx数组排序，排序依据是$nums[idx[i]]$大的优先。这样，$idx$的前$k$个元素就是$nums$最大的$k$个数的下标了。

返回这$k$个下标对应的$nums$中的元素之前，不要忘了对$idx$再按从小到大的顺序排个序，因为返回的“$nums$子序列”是要保持原有顺序的。

• 时间复杂度$O(n\log n)$，其中$n=len(nums)$
• 空间复杂度$O(\log n)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-07-03 21:31:48
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-07-06 00:06:51
 */
class Solution {
public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        vector<int> idx(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            idx[i] = i;
        }
        sort(idx.begin(), idx.end(), [&nums](int i, int j) {
            return nums[i] > nums[j];
        });
        idx.resize(k);
        sort(idx.begin(), idx.end());
        for (int &t : idx) {
            t = nums[t];
        }
        return idx;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-07-03 21:31:48
LastEditors: LetMeFly.xyz
LastEditTime: 2025-07-06 00:09:39
'''
from typing import List

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        idx = [i for i in range(len(nums))]
        idx.sort(key=lambda i : -nums[i])
        idx = idx[:k]
        idx.sort()
        return [nums[i] for i in idx]

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-07-03 21:31:48
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-07-06 22:03:44
 */
import java.util.Arrays;

class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        Integer[] idx = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) {
            idx[i] = i;
        }
        Arrays.sort(idx, (i, j) -> nums[j] - nums[i]);
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = idx[i];
        }
        Arrays.sort(ans);
        for (int i = 0; i < k; i++) {
            ans[i] = nums[ans[i]];
        }
        return ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-07-03 21:31:48
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-07-06 22:16:49
 */
package main

import "sort"

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]]  // 不可以nums[i] > nums[j]，因为排序过程中idx[i]可能不再是i 
    })
    idx = idx[:k]
    sort.Ints(idx)
    for th, i := range idx {
        idx[th] = nums[i]
    }
    return idx
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源