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

在这个问题中，我们给定一个包含 n 个整数的数组 arr[] 和一个数字 d。我们的任务是创建一个程序，用 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。否则，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<<"The maximum sum of pairs with specific difference is "<<CalcmaxPairSum(arr, n, d);
   return 0;
}

输出

The maximum sum of pairs with specific difference is 47

sudhir sharma

更新于: 2020-12-09

161 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习