Maximum sum of pairs with specific difference - GeeksforGeeks

Maximum sum of pairs with specific difference - GeeksforGeeks

Given an array of integers and a number k. We can pair two number of array if difference between them is strictly less than k. The task is to find maximum possible sum of disjoint pairs. Sum of P pairs is sum of all 2P numbers of pairs.

Input  : arr[] = {3, 5, 10, 15, 17, 12, 9}, K = 4
Output : 62
Then disjoint pairs with difference less than K are,
(3, 5), (10, 12), (15, 17)    
So maximum sum which we can get is 3 + 5 + 12 + 10 + 15 + 17 = 62
Note that an alternate way to form disjoint pairs is,
(3, 5), (9, 12), (15, 17), but this pairing produces lesser sum.

First we sort the given array in increasing order. Once array is sorted, we traverse the array. For every element, we try to pair it with its previous element first. Why do we prefer previous element? Let arr[i] can be paired with arr[i-1] and arr[i-2] (i.e. arr[i] – arr[i-1] < K and arr[i]-arr[i-2] < K). Since the array is sorted, value of arr[i-1] would be more than arr[i-2]. Also, we need to pair with difference less than k, it means if arr[i-2] can be paired, then arr[i-1] can also be paired in a sorted array.
Now observing the above facts, we can formulate our dynamic programming solution as below,
Let dp[i] denotes the maximum disjoint pair sum we can achieve using first i elements of the array. Assume currently we are at i’th position, then there are two possibilities for us.

  Pair up i with (i-1)th element, i.e. 
      dp[i] = dp[i-2] + arr[i] + arr[i-1]
  Don't pair up, i.e. 
      dp[i] = dp[i-1] 

Above iteration takes O(N) time and sorting of array will take O(N log N) time so total time complexity of the solution will be O(N log N)

    static int maxSumPairWithDifferenceLessThanK(int arr[],

                                               int N, int K)

    {

          

        // Sort input array in ascending order.

        Arrays.sort(arr);

      

        // dp[i] denotes the maximum disjoint pair sum

        // we can achieve using first i elements

        int dp[] = new int[N];

      

        // if no element then dp value will be 0

        dp[0] = 0;

      

        for (int i = 1; i < N; i++)

        {

            // first give previous value to dp[i] i.e.

            // no pairing with (i-1)th element

            dp[i] = dp[i-1];

      

            // if current and previous element can form a pair

            if (arr[i] - arr[i-1] < K)

            {

                  

                // update dp[i] by choosing maximum between

                // pairing and not pairing

                if (i >= 2)

                    dp[i] = Math.max(dp[i], dp[i-2] + arr[i] +

                                                    arr[i-1]);

                else

                    dp[i] = Math.max(dp[i], arr[i] + arr[i-1]);

            }

        }

      

        // last index will have the result

        return dp[N - 1];

    }







    static int maxSumPairWithDifferenceLessThanK(int arr[], 

                                               int N, int k)

    {

        int maxSum = 0;

      

        // Sort elements to ensure every i and i-1 is closest

        // possible pair

        Arrays.sort(arr);

      

        // To get maximum possible sum, iterate from largest

        // to smallest, giving larger numbers priority over 

        // smaller numbers.

        for (int i = N-1; i > 0; --i)

        {

            // 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] < arr[i]-arr[i-2] and

            //     so on.

            if (arr[i] - arr[i-1] < k)

            {

                //Assuming only positive numbers.

                maxSum += arr[i];

                maxSum += arr[i-1];

      

                //When a match is found skip this pair

                --i;

            }

        }

      

        return maxSum;

    }

https://www.geeksforgeeks.org/pairs-difference-less-k/

Given an array of n integers, We need to find all pairs with difference less than k

Examples :

Input : a[] = {1, 10, 4, 2}
        K = 3
Output : 2
We can make only two pairs 
with difference less than 3.
(1, 2) and (4, 2)

    static int countPairs(int a[], int n, int k)

    {

        // to sort the array.

        Arrays.sort(a);

      

        int res = 0;

        for (int i = 0; i < n; i++) 

        {

      

            // Keep incrementing result while

            // subsequent elements are within

            // limits.

            int j = i + 1; 

            while (j < n && a[j] - a[i] < k) 

            {

                res++;

                j++;

            }

        }

        return res;

    }