特定の違いを持つペアの最大合計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

ソリューションアプローチ

この問題の簡単で明白な解決策は、配列のすべての有効なペアを作成し、合計を見つけて、すべての合計の最大値を返すことです。しかし、このソリューションは効率的ではありません。

この問題の効率的な解決策は、動的プログラミングアプローチを使用することです。ここでは、最大値を構成する最適なペアを見つけます。このために、ソートされた配列を使用するので、最初にgivenarrayをソートしてから、それを操作します。合計を見つけるために、配列を使用して、現在の要素までのペアの最大合計を格納します。このために、現在の要素と前の要素がペアになっているかどうかを確認します。はいの場合、配列までペアの合計を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