PROBLEM LINK:
Author: Devendra Agarwal
Tester: Surya Kiran
Editorialist: Amit Pandey
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given an array A of N positive integers, you can pair two numbers if difference between them is D. Find out maximum sum of disjoint sum of pairs you can obtain.
QUICK EXPLANATION:
Sort the array A in increasing (non-decreasing) order. Let us go from the end to beginning of the array. If last number should be matched, then the best number with which it can be matched is the next-to-last one only because the difference between numbers can only increase if we consider elements prior to the next-to-last one (i.e. element at positions N - 2 or less). Remove the last element and optionally the next-to-last element if a pair is made and keep doing the same for the remaining array.
Explanation
Greedy solution
Let us look only at the last number i.e. the number at position N. If we want to match this number of any number, then we will prove that it’s best to match it with the next-to-last number, i.e., at position N-1. First, as the array is sorted, if we go from index N to 1, difference between A[i] and A[N] will only increase, so the least difference will be only at position N-1. Now, let’s assume that N is matched to some i other than N-1, then we can always swap this assignment and get a better solution which leads to contradiction.
So, for last number, we find whether the difference between last and next last number is less than D or not. If yes, then we form a pair. Now, we will remove the last element and its pairing element too (if one exists), and solve the problem for the remaining array similarly.
ans = 0; for i = N to 2: if (A[i] - A[i-1] < D) ans += A[i] + A[i-1]; i -= 2; else i -= 1;
Time complexity of the algorithm is dominated by the sorting part, i.e. \mathcal{O} (N * log N) time.
Dynamic programming based solution
Let dp[i] denotes the maximum disjoint pair sum we can get using first i elements of the array.
Assume, we are currently at i-th position, there are two possibilities for us.
- Pair up i with i-1, i.e. dp[i] = dp[i-2] + A[i] + A[i-1]
- Don’t pair up, i.e. dp[i] = dp[i-1]
Pseudo code of this idea follows.
int dp[N+1]; for i from 1 to N: dp[i] = max(dp[i-2] + A[i] + A[i-1], dp[i-1]); ans = 0; for i from 1 to N: ans = max(ans, dp[i]);
Time complexity of this algorithm is \mathcal{O}(N * log N) (for sorting) + \mathcal{O}(N) (for DP). Overall, we can say that time complexity is \mathcal{O}(N * log N).
