数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++程序中至少包含k个距离元素的最大和子序列
在这个问题中，我们得到一个大小为n的数组arr[]和一个数字k。我们的任务是编写一个程序来查找至少包含k个距离元素的最大和子序列。
问题描述 − 我们需要找到子数组的和，这些子数组的元素取自索引之间距离至少为k的数组，并且和最大化。
让我们来看一个例子来理解这个问题：
输入
arr[] = {2, 3, 7, 9, 2, 8, 3}输出
15
解释
All subsequences that satisfy the given condition,
{2, 9, 3}, Sum = 14
{3, 2}, Sum = 5
{7, 8}, Sum = 15解决方案方法
解决这个问题的一个简单方法是找到所有满足给定条件的可能的子数组。找到所有数组的和，并返回所有和中的最大值。
解决这个问题的一个更有效的方案是使用动态规划方法，创建一个数组来存储直到当前元素的最大和。对于当前元素，我们可以将其考虑在和中，也可以将其排除在和之外，选择哪个可以增加直到当前索引的和。
如果我们将其考虑在和中，sum[i] = sum[i + k + 1] + arr[i+1]；否则将其排除在和之外，sum[i] = sum[i+1]。最后返回最大和，即sum[0]。
示例
程序说明了我们解决方案的工作原理：
#include <bits/stdc++.h>
using namespace std;
int calcMaxSubSeqSum(int arr[], int N, int k){
int maxSumDP[N];
maxSumDP[N − 1] = arr[N − 1];
for (int i = N − 2; i >= 0; i−−) {
if (i + k + 1 >= N)
maxSumDP[i] = max(arr[i], maxSumDP[i + 1]);
else
maxSumDP[i] = max(arr[i] + maxSumDP[i + k + 1], maxSumDP[i + 1]);
}
return maxSumDP[0];
}
int main() {
int N = 10, k = 2;
int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 };
cout<<"The maximum sum subsequence with at−least k distant elements is "<<calcMaxSubSeqSum(arr, N, k);
return 0;
}输出
The maximum sum subsequence with at-least k distant elements is 230
更新于：2020年12月9日
245 次浏览
广告