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

悠悠 2024-03-30 11:58 17阅读 0赞

## 【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的整数子序列。
     * 子序列定义为从一个数组里删除一些元素后，不改变剩下元素的顺序得到的数组。
     * <p>
     * 输入：nums = [2,1,3,3], k = 2
     * 输出：[3,3]
     * 解释：
     * 子序列有最大和：3 + 3 = 6 。
     */
    public class Solution {
        
        // nums = [3,4,3,3], k = 2
        public int[] maxSubsequence(int[] nums, int k) {
        
            // 4
            int 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 <iostream>
    #include <vector>
    
    using namespace std;
    
    class Solution {
        
    public:
        vector<int> maxSubsequence(vector<int> &nums, int k) {
        
            vector<pair<int, int>> idx;
            vector<int> ans;
            for (int i = 0; i < nums.size(); ++i) {
        
                const auto &num = nums[i];
                //idx.push_back(pair<int, int>(i, num));
                idx.emplace_back(i, num);
            }
            // 按照数值nums[idx]从大到小排序
            sort(idx.begin(), idx.end(), [](pair<int, int> a, pair<int, int> b) {
         return a.second > b.second; });
            // 按照索引idx从小到大进行排列
            sort(idx.begin(), idx.begin() + k, [](pair<int, int> a, pair<int, int> b) {
         return a.first < b.first; });
            // 复制结果
            for (int i = 0; i < k; ++i) {
        
                ans.push_back(idx[i].second);
            }
            return ans;
        }
    };
    
    
    int main() {
        
        vector<int> ret = {
        2, 3, -1, 4};
        for (const auto &item: (new Solution)->maxSubsequence(ret, 2)) {
        
            cout << item << endl;
        }
    
    }

**Output**

3
    4

![在这里插入图片描述][e7530c235fc9457e8a7b3f31f0762e1f.png]  
时间复杂度：O(nlogn)，其中 n 为 nums 的长度。即为对辅助数组排序的时间复杂度。  
空间复杂度：O(n)，即为辅助数组的空间开销。

[e7530c235fc9457e8a7b3f31f0762e1f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e3e1c9811e6b4bbdb40f415143f273e1.png