Maximum sum of pairs with specific difference in C++

In this tutorial, we will be discussing a program to find maximum sum of pairs with specific difference.

For this we will be provided with an array containing integers and a value K. Our task is to pair elements having difference less than K and finally find the maximum sum of the elements in disjoint sets.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; //returning maximum sum of disjoint pairs int maxSumPairWithDifferenceLessThanK(int arr[], int N, int K){    sort(arr, arr+N);    int dp[N];    dp[0] = 0;    for (int i = 1; i < N; i++) {       dp[i] = dp[i-1];       if (arr[i] - arr[i-1] < K) {          if (i >= 2)             dp[i] = max(dp[i], dp[i-2] + arr[i] + arr[i-1]);          else             dp[i] = max(dp[i], arr[i] + arr[i-1]);       }    }    return dp[N - 1]; } int main() {    int arr[] = {3, 5, 10, 15, 17, 12, 9};    int N = sizeof(arr)/sizeof(int);    int K = 4;    cout << maxSumPairWithDifferenceLessThanK(arr, N, K);    return 0; }

Output

62