C ++程序中具有至少k个远距离元素的最大和子序列
在这个问题中，我们得到了大小为n且数字为k的数组arr[]。我们的任务是创建一个程序，以找到至少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