8 find subsequences with a maximum length of K

8  Find and the maximum length is K The subsequence

author : Turbo The time limit : 1S chapter :  curriculum design

Problem description :

Give you an array of integers nums And an integer k . You need to find nums The middle length is k The subsequence , And this subsequence and Maximum .

Please return arbitrarily A length of k Integer subsequence of .

Subsequence Defined as deleting some elements from an array , The array obtained without changing the order of the remaining elements .

Example 1：

Input ：

4

2 1 3 3

2

Output ：

3 3

explain ：

Subsequences have maximum sum ：3 + 3 = 6 .

Example 2：

Input ：

4

-1 -2 3 4

3

Output ：

-1 3 4

explain ：

Subsequences have maximum sum ：-1 + 3 + 4 = 6 .

Example 3：

Input ：

4

3 4 3 3

2

Output ：

3 4

explain ：

Subsequences have maximum sum ：3 + 4 = 7 .

Another feasible subsequence is [4, 3] .

Enter description :

Enter three lines ：

The first line is an integer n Representative array nums The length of .

Second line input n An integer represents an array nums The elements of .

The third is an integer k.

Tips ：

    1 <= n <= 1000

    -10^5 <= nums[i] <= 10^5

    1 <= k <= n

Output one line k An integer represents the result , Integers are separated by spaces .

Input example :

5
-3 4 4 2 1
2

----------

The output shows that :

4 4 

-------------------

The structure contains its data And his array number

Sort the data first Get the biggest ones

Then for these largest structures Sort the array number Array small front row then for Before cyclic output n Just one

#include<iostream>
#include<algorithm>
using namespace std;

struct student
{
	int number;
	int data;
};

bool cmp(student x, student y)
{
	return x.data > y.data;
}

bool cmp2(student x, student y)
{
	return x.number < y.number;
}
int main()
{
	student arr[1000];
	int n = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i].data;
		arr[i].number = i;
	}
	int k = 0;
	cin >> k;
	sort(arr, arr + n, cmp);
	sort(arr, arr + k, cmp2);
	for (int i = 0; i < k; i++)
	{
		cout << arr[i].data << " ";
	}

	return 0;
}