一个子序列的最大和数，以使C ++程序中数组中的两个元素都不在距离 <K处出现

在这个问题中，我们得到了大小为n且整数为k的数组arr []。我们的任务是创建一个程序，以找到一个子序列的最大和，以使两个元素都不出现在距离<K的数组中。

问题描述-我们需要找到考虑子元素彼此相距k距离的子序列的最大和。

让我们举个例子来了解这个问题，

输入项

arr[] = {6, 2, 5, 1, 9, 11, 4} k = 2

输出结果

16

说明

All possible sub−sequences of elements that differ by k or more.
{6, 1, 4}, sum = 11
{2, 9}, sum = 11
{5, 11}, sum = 16
{1, 4}, sum = 5
...
maxSum = 16

解决方法

解决该问题的方法是使用动态编程。对于该解决方案，我们将找到最大可能的和，直到数组的当前元素为止。并将其存储到DP [i]中，为此，我们将找到最大可能的和。对于第i个索引，我们需要检查是否添加当前索引值会增加子序列总和。

if( DP[i − (k+1)] + arr[i] > DP[i − 1] )
−> DP[i] = DP[i − (k+1)] + arr[i]
otherwise DP[i] = DP[i−1]

动态数组的最大元素给出最大子序列和。

算法

初始化-

maxSumSubSeq = −1, maxSumDP[n]

第1步-

Initialize maxSumDP[0] = arr[0]

第2步-

Loop for i −> 1 to n.

步骤2.1 -

if i < k −> maxSumDP[i] = maximum of arr[i] or
maxSumDP[i− 1].

步骤2.2 -

else, maxSumDP[i] = maximum of arr[i] or maxSumDP[i − (k + 1)] + arr[i].

第3步-

Find the maximum value of all elements from maxSumDP and store
it to maxSumSubSeq.

第4步-

Return maxSumSubSeq

示例

该程序说明了我们解决方案的工作原理，

#include <iostream>
using namespace std;
int retMaxVal(int a, int b){
   if(a > b)
   return a;
   return b;
}
int calcMaxSumSubSeq(int arr[], int k, int n) {
   int maxSumDP[n];
   int maxSum = −1;
   maxSumDP[0] = arr[0];
   for (int i = 1; i < n; i++){
      if(i < k ){
         maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i − 1]);
      }
      else
      maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i − (k +
      1)] + arr[i]);
   }
   for(int i = 0; i < n; i++)
   maxSum = retMaxVal(maxSumDP[i], maxSum);
   return maxSum;
}
int main() {
   int arr[] = {6, 2, 5, 1, 9, 11, 4};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 2;
   cout<<"The maximum sum possible for a sub−sequence such
   that no two elements appear at a distance < "<<k<<" 在数组中是 "<<calcMaxSumSubSeq(arr, k, n);
   return 0;
}

输出结果

The maximum sum possible for a sub−sequence such that no two
elements appear at a distance < 2 在数组中是 16