【LeetCode】2099. 找到和最大的长度为 K 的子序列

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

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

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

示例

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

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

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

实现

Java

package cn.com.codingce.数组与矩阵.找到和最大的长度为K的子序列;import java.util.Arrays;/*** 给你一个整数数组nums和一个整数k。你需要找到nums中长度为 k的 子序列，且这个子序列的和最大。* 请你返回 任意 一个长度为k的整数子序列。* 子序列定义为从一个数组里删除一些元素后，不改变剩下元素的顺序得到的数组。* 
* 输入：nums = [2,1,3,3], k = 2* 输出：[3,3]* 解释：* 子序列有最大和：3 + 3 = 6 。*/
public class Solution {// nums = [3,4,3,3], k = 2public int[] maxSubsequence(int[] nums, int k) {// 4int len = nums.length;// idxMap：辅助数组，用来存储数值和索引int[][] idxMap = new int[len][2];for (int i = 0; i < len; i++) {idxMap[i][1] = nums[i];idxMap[i][0] = i;}// 按照数值nums[idx]从大到小排序Arrays.sort(idxMap, (a, b) -> b[1] - a[1]);System.out.println("=====sort");for (int[] num : idxMap) {for (int n : num) {System.out.print(n + "\t");}System.out.println();}// 按照索引idx从小到大进行排列Arrays.sort(idxMap, 0, k, (a, b) -> a[0] - b[0]);System.out.println("=====sort2");for (int[] num : idxMap) {for (int n : num) {System.out.print(n + "\t");}System.out.println();}// 复制结果int[] res = new int[k];for (int idx = 0; idx < k; idx++) {// 返回值res[idx] = idxMap[idx][1];}return res;}public static void main(String[] args) {new Solution().maxSubsequence(new int[]{-1, -2, 3, 4}, 3);}
}

Output

=====sort
3	4	
2	3	
0	-1	
1	-2	
=====sort2
0	-1	
2	3	
3	4	
1	-2

-1, 3, 4

C++

//
// Created by mxz on 2022/12/24.
//
#include 
#include using namespace std;class Solution {
public:vector maxSubsequence(vector &nums, int k) {vector> idx;vector ans;for (int i = 0; i < nums.size(); ++i) {const auto &num = nums[i];//idx.push_back(pair(i, num));idx.emplace_back(i, num);}// 按照数值nums[idx]从大到小排序sort(idx.begin(), idx.end(), [](pair a, pair b) { return a.second > b.second; });// 按照索引idx从小到大进行排列sort(idx.begin(), idx.begin() + k, [](pair a, pair b) { return a.first < b.first; });// 复制结果for (int i = 0; i < k; ++i) {ans.push_back(idx[i].second);}return ans;}
};int main() {vector ret = {2, 3, -1, 4};for (const auto &item: (new Solution)->maxSubsequence(ret, 2)) {cout << item << endl;}}

Output

3
4

时间复杂度：O(nlogn)，其中 n 为 nums 的长度。即为对辅助数组排序的时间复杂度。
空间复杂度：O(n)，即为辅助数组的空间开销。