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