Maximum sum of pairs with specific difference

Difficulty Level Easy
Frequently asked in Accolite Coursera Delhivery Fourkites Snapdeal
Array Dynamic ProgrammingViews 2406

The problem “Maximum sum of pairs with specific difference” states that you are given an array of integers and an integer K. Then we are asked to find out the maximum sum of independent pairs. We can pair two integers if they have an absolute difference of less than K. So, we are required to find the maximum sum of such x pairs that is 2x numbers.

Example

Maximum sum of pairs with specific difference

42, 43, 4, 5, 6, 12
96

Explanation

We pick 42, 43, and 5, 6. We had options among 4, 5, and 6. So, we take the maximum value among them making the result = 96.

Approach

The problem asks us to find the maximum sum that can be achieved if we pair some elements of the array. We can pair elements under the imposed condition that the elements should have an absolute difference of less than K. Before solving the problem, we sort the array. This way we are pruning our search space. Consider we had an unsorted array. Then we would have to traverse all the elements for pairing an element. But after sorting we know that the largest element is just the element which is previous to it. So we check if the condition is satisfied.

If the condition is satisfied, we pair the previous and current element and add the result for the problem until the last second element(from the current element). But if the condition is not satisfied. We leave the pairing and the result is the same as that of until the previous element. More formally, result[i] = result[i-2] + input[i] + input[i-2], if pairing is done else result[i] = result[i-1]. Here this result array is our DP array because we are storing the result of the smaller subproblems. We combine the result of these smaller subproblems to find the result of the original problem as we do in bottom-up DP.

Code

C++ code to find the maximum sum of pairs with specific difference

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int input[] = {42, 43, 4, 5, 6, 12};
    int n = sizeof(input)/sizeof(int);
    int K = 4;
    sort(input, input+n);
    int dp[n];
    memset(dp, 0, sizeof dp);
    for(int i=1;i<n;i++){
        dp[i] = dp[i-1];
        if(input[i]-input[i-1] < K)
            dp[i] = max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
    }
    cout<<dp[n-1];
    return 0;
}

96

Java code to find the maximum sum of pairs with specific difference

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int input[] = {42, 43, 4, 5, 6, 12};
      int n = input.length;
      int K = 4;
      Arrays.sort(input);
      int dp[] = new int[n];
      dp[0] = 0;
      for(int i=1;i<n;i++){
          dp[i] = dp[i-1];
          if(input[i]-input[i-1] < K)
              dp[i] = Math.max(dp[i], (i>=2 ? dp[i-2] : 0) + input[i] + input[i-1]);
      }
    System.out.println(dp[n-1]);
  }
}
96

Complexity Analysis

Time Complexity 

O(NlogN), this is because we had initially sorted the array. And merge sort and other sorting algorithms can sort the array in O(NlogN). If we were provided with a sorted input, we could have solved the problem in O(N) time.

Space Complexity

O(N), this space is required for sorting the array. Even if we had not made the DP array and would have used the same input array for DP table. That solution still has the same space complexity because this space is required for sorting.

Translate »