【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 Listclass 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 mainimport "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和我的個人博客，原創不易，轉載經作者同意后請附上原文鏈接哦~

千篇源碼題解已開源