8 找到和最大的长度为 K 的子序列

8 找到和最大的长度为 K 的子序列

作者: Turbo时间限制: 1S章节: 课程设计

问题描述 :

给你一个整数数组 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 

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

结构体里面包含他的数据 和他的数组编号

先对数据排序 得到最大的几个

然后对这几个最大的结构体 进行数组编号排序 数组小的排前面 然后for循环输出前n个就行了

#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;
}