Maximum sum of pairs with specific difference | C ++ program to find maximum pair sum whose difference is less than K ; Method to return maximum sum we can get by finding less than K difference pairs ; Sort elements to ensure every i and i - 1 is closest possible pair ; To get maximum possible sum , iterate from largest to smallest , giving larger numbers priority over smaller numbers . ; Case I : Diff of arr [ i ] and arr [ i - 1 ] is less then K , add to maxSum Case II : Diff between arr [ i ] and arr [ i - 1 ] is not less then K , move to next i since with sorting we know , arr [ i ] - arr [ i - 1 ] < rr [ i ] - arr [ i - 2 ] and so on . ; Assuming only positive numbers . ; When a match is found skip this pair ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSumPair ( int arr [ ] , int N , int k ) { int maxSum = 0 ; sort ( arr , arr + N ) ; for ( int i = N - 1 ; i > 0 ; -- i ) { if ( arr [ i ] - arr [ i - 1 ] < k ) { maxSum += arr [ i ] ; maxSum += arr [ i - 1 ] ; -- i ; } } return maxSum ; } int main ( ) { int arr [ ] = { 3 , 5 , 10 , 15 , 17 , 12 , 9 } ; int N = sizeof ( arr ) / sizeof ( int ) ; int K = 4 ; cout << maxSumPair ( arr , N , K ) ; return 0 ; }