个人任务8.找到和最大的长度为 K 的子序列

Bertha 。 2023-09-28 13:31 40阅读 0赞

> **问题描述：**  
> 给你一个整数数组 nums 和一个整数 k 。你需要找到 nums 中长度为 k 的子序列 ，且这个子序列的 和 最大 。  
> 请你返回 任意 一个长度为 k 的整数子序列。  
> 子序列 定义为从一个数组里删除一些元素后，不改变剩下元素的顺序得到的数组。  
> 示例 1：  
> 输入：  
> 4  
> 2 1 3 3  
> 2  
> 输出：  
> 3 3  
> 解释：  
> 子序列有最大和：3 + 3 = 6 。  
> 示例 2：  
> 输入：  
> 4  
> \-1 -2 3 4  
> 3  
> 输出：  
> \-1 3 4  
> 解释：  
> 子序列有最大和：-1 + 3 + 4 = 6 。  
> 示例 3：  
> 输入：  
> 4  
> 3 4 3 3  
> 2  
> 输出：  
> 3 4  
> 解释：  
> 子序列有最大和：3 + 4 = 7 。  
> 另一个可行的子序列为 \[4, 3\] 。

> **输入说明：**  
> 输入三行：  
> 第一行为一个整数n代表数组nums的长度。  
> 第二行输入n个整数代表数组nums的元素。  
> 第三行为一个整数k。  
> 提示：  
> 1 <= n <= 1000  
> \-10^5 <= nums\[i\] <= 10^5  
> 1 <= k <= n

> **输出说明：**  
> 输出一行k个整数表示结果，整数间用空格隔开。

> **输入范例：**  
> 5  
> \-3 4 4 2 1  
> 2

> **输出范例：**  
> 4 4

#include<iostream>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<stdlib.h>
    #include<stdio.h>
    #include<fstream>
    #include<iomanip>
    #include<utility>
    using namespace std;
    int a[10001]={
        0},b[10001]={
        0};
    
    bool cmp1(pair<int,int> we,pair<int,int> wk){
        
        return we.second>wk.second;//对数组的值进行降序排列
    }
    
    bool cmp2(pair<int,int> we,pair<int,int> wk){
        
        return we.first<wk.first;//对数组的下标进行升序排列
    }
    
    int main(){
        
        int n,k;
        cin>>n;
        pair<int,int> dui[n];
        for(int i=0;i<n;++i){
        
            cin>>a[i];
            dui[i]=make_pair(i,a[i]);
        }
        cin>>k;
        stable_sort(dui,dui+n,cmp1);//将数组按值从大到小排列
        stable_sort(dui,dui+k,cmp2);//前k个值的下标从小到大排列
        for(int i=0;i<k;++i)
            cout<<dui[i].second<<" ";
        return 0;
    }