Maximum Sum With Specific Difference

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
5 upvotes
Asked in companies
AmazonAmerican ExpressAcko

Problem statement

You are given an array of integers and a number ‘K’. You can pair two elements in the array 'ARR' if the absolute difference between them is strictly less than ‘K’. Your task is to find the maximum possible sum of disjoint pairs among all the pairs of numbers you can obtain.

The sum of a pair is the sum of the elements in the pair.

For Example: 
Input: ARR[] = {3, 5, 10, 15, 17, 12, 9}, K = 4
Output: 62

Then disjoint pairs with the absolute 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: 
Note that an alternate way to form disjoint pairs is, (3, 5), (9, 12), (15, 17), but this pairing produces a lesser sum.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases to run.

The first line of each test contains an integer 'N', denoting the size of the array 'ARR' which would be given.

The next line is the given array values in a space-separated set of ‘N’ elements.

The last line of every test case is s single integer denoting ‘K’.
Output format: 
For every test case, you need to print the maximum possible sum of disjoint pairs. 

Output for each test case will be printed in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 3000
1 <= ARR[i] <=1000
1 <= K < 1000

Time limit: 1 sec
Sample Input 1:
2
7
3 5 10 15 17 12 9
4
4
5 15 10 300
12
Sample Output 1:
62
25
Explanation Of Sample Input 1:
For First test case: 
Then disjoint pairs with a difference less than K (Here K = 4) are, (3, 5), (10, 12), (15, 17)  
So maximum sum which we can get is 3 + 5 + 12 + 10 + 15 + 17 = 62

For Second test case:
Then disjoint pairs with a difference less than K (Here K = 12) are, (10, 15)  
So the maximum sum which we can get is 10 + 15 = 25
Sample Input 2:
2
5
1 2 3 4 5
2
5
2 3 12 53 28 
5
Sample Output 2:
14
5
Explanation Of Sample Input 2:
For First test case: 
Then disjoint pairs with a difference less than K (Here K = 2) are, (3, 5), (2, 4)
So maximum sum which we can get is 3 + 5 + 2 + 4 = 14

For Second test case:
Then disjoint pairs with a difference less than K (Here K = 5) are, (2, 3)  
So the maximum sum which we can get is 2 + 3 = 5
Hint

Try to arrange them in specific order and then find all pairs.

Approaches (2)
Sorting

Approach: We sort the given array in increasing order. For every element, we try to pair it with its previous element first. Since the array is sorted, the value of ‘ARR[i]’ would be more than ‘ARR[i - 1]’. We need to pair with a difference less than ‘K’, which means if 'ARR[i - 2]' can be paired, then ‘ARR[i - 1]’ can also be paired in a sorted array. Here, we prefer the previous element so that if ‘ARR[i]’ - ‘ARR[i - 1]’ < 'K', then definitely the previous element would give us a bigger sum as the array is sorted. Now observing the above facts, we can formulate our dynamic programming solution as follows:

 

Let ‘DP[i]’ denote the maximum disjoint pair sum we can achieve using first ‘i’ elements of the array. Assume currently we are at ith 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]

or don't pair up, i.e. DP[i] = DP[i - 1] 

 

Now, taking advantage of the above strategy, our dynamic programming solution can be as given below:

 

Steps:

  1. Let ‘DP[i]’ denote the maximum disjoint pair sum we can achieve using the first ‘i’ elements of the array. Now, assume that currently, we are at the ith position, first give the previous value to ‘DP[i]’ (i.e. ‘DP[i]' = ‘DP[i - 1]’) and if the difference between the adjacent array then to maximize ‘DP[i]’ we can take one of the two possibilities for us.
  2. We can either pair up ‘i’ with (i - 1)th element, i.e.
    • ‘DP[i]’ = max('DP[i]', ‘DP[i-2] + ARR[i] + ARR[i - 1]')
  3. Or either don't pair up, i.e.
    • ‘DP[i]’ = max('DP[i]', ‘ARR[i] + ARR[i - 1]’)
  4. Now, We return the last element in the dp array i.e. ‘DP[N - 1]’, which now contains the maximum sum of the disjoint pairs having a difference less than ‘K’ i.e.
    • return ‘DP[N - 1]’.
Time Complexity

O(N * log(N)), where ‘N’ is the number of elements present in the array.

 

Now, since they are sorted which takes O(N * log(N)) while the above iteration takes O(N) time, therefore, the total time complexity of the solution will be O(N * log(N))

Space Complexity

O(N), where N is the number of elements of the array.

 

Since a dp array of size ‘N’ is used to keep track of the maximized sum of ith elements in every iteration, therefore, space of O(N) would be required.

Code Solution
(100% EXP penalty)
Maximum Sum With Specific Difference
Full screen
Console