具有特定差异的C ++程序对的最大和

在这个问题中，我们得到了一个由n个整数和一个数字d组成的数组arr []。我们的任务是创建一个程序，以查找在c ++中具有特定差异的最大对数之和。

问题描述-我们将以对的元素差小于d的方式找到对。所有这些对的总和应为最大值。

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

输入项

arr[] = {5, 9, 11, 7, 2, 12, 3} d = 5

输出结果

47

说明

Pairs that contribute to maximum sum: (3, 5), (7, 9), (11, 12). Sum = 3 + 5 + 7 + 9 + 11 + 12 = 47

解决方法

一个简单而明显的解决方案是创建所有有效的数组对，然后找到总和并返回所有总和的最大值。但是这种解决方案效率不高。

解决该问题的有效方法是使用动态编程方法。在这里，我们将找到构成最大和的最优对。为此，我们将使用排序数组，因此首先我们将对给定数组进行排序，然后对其进行操作。为了找到和，我们将使用一个数组来存储对的最大和，直到当前元素为止。为此，我们将检查当前元素和先前元素是否成对。如果是，我们将对和加到maxSum直到数组。否则，最大和将保持原样。

算法

Initialize: DP[n]

第1步-

For array arr[].

第2步

DP[0] = 0;

第3步-

loop for i −> 1 to n

步骤3.1 -

check if pairs with the previous element is possible. if(arr[i]
− arr[i−1] < d).

步骤3.2 -

if Yes, check if the current pair sum results in a greater
value than the last considered sum and add the maximum value to the
current sum. i.e. if( (DP[i−2] + arr[i−1] + arr[i]) > (DP[i−1])) −>
DP[i] = (DP[i−2] + arr[i−1] + arr[i]), else −> DP[i] = DP[i−1].

步骤3.3 -

an exception is for value i = 1, where no value of DP[i−2] is
possible, in this case, DP[i−2] is not considered as it is the first pair
sum.

第4步-

Return DP[n−1].

示例

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

#include <bits/stdc++.h>
using namespace std;
int CalcmaxPairSum(int arr[], int n, int d) {
   sort(arr, arr+n);
   int maxSumDP[n];
   maxSumDP[0] = 0;
   for (int i = 1; i < n; i++) {
      maxSumDP[i] = maxSumDP[i−1];
      if (arr[i] − arr[i−1] < d) {
         if (i >= 2)
         if(maxSumDP[i] < (maxSumDP[i−2] + arr[i−1] +
         arr[i]))
         maxSumDP[i] = (maxSumDP[i−2] + arr[i−1] +
         arr[i]);
         else
         if(maxSumDP[i] < (arr[i−1] + arr[i]))
         maxSumDP[i] = arr[i−1] + arr[i];
      }
   }
   return maxSumDP[n−1];
}
int main() {
   int arr[] = {5, 9, 11, 7, 2, 12, 3};
   int n = 7, d = 5;
   cout<<"具有特定差异的对的最大和为 "<<CalcmaxPairSum(arr, n, d);
   return 0;
}

输出结果

具有特定差异的对的最大和为 47