Home » Technical Interview Questions » Dynamic Programming Interview Questions » Maximum sum of pairs with specific difference

Maximum sum of pairs with specific difference


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.

READ  Print Maximum Length Chain of Pairs

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.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup