Last Updated: 10 Mar, 2021
Maximum Sum With Specific Difference
Moderate
Asked in companies
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.
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
Approaches
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:
- 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.
- 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]')
- Or either don't pair up, i.e.
- ‘DP[i]’ = max('DP[i]', ‘ARR[i] + ARR[i - 1]’)
- 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]’.
Approach: We can sort the array to ensure that every i’th and (i-1)st element is the closest possible pair. Now to get the maximum possible sum, we can iterate from largest to smallest, giving larger numbers priority over smaller numbers.
Algorithm:
- Sort all the elements present inside the array. Initialize ‘MAXSUM' to 0.
- Now for each ‘i’ from ‘N’ - 1 to 1:
- If the difference of ‘ARR[i]’ and ‘ARR[i - 1]’ is less than ‘K’, then add the pair to the ‘MAXSUM'.
- If the difference between ‘ARR[i]’ and ‘ARR[i - 1]’ is not less then ‘K’, we continue our iteration.
- We finally return ‘MAXSUM'.
Similar problems