具有特定差异的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