316. Maximum Sum of Pairs With Specific Difference

Given an array of n integers and an integer k, choose some number of disjoint pairs of elements (each array element used in at most one pair) such that within each pair the absolute difference is strictly less than k, so as to maximize the sum of all chosen (paired) elements.

Input: The first line contains an integer n. The second line contains n space-separated integers, the array. The third line contains an integer k. Output: Print a single integer - the maximum achievable sum from disjoint pairs whose absolute difference is strictly less than k.

1 <= n <= 10^4

This 'sort first, then only consider adjacent pairings' technique is a recurring pattern whenever a problem involves pairing elements to satisfy a difference-based constraint - the same idea underlies 'Minimum Sum of Absolute Differences of Pairs of Two Arrays' from the Linked List category too.

Choose disjoint pairs of array elements (each with a small enough difference) to maximize their combined sum. Brute force: Try every possible way of pairing up elements directly - this is combinatorially expensive (choosing which elements to pair), impractical for n up to 10^4. Optimised: Sorting first proves that only ADJACENT pairs in sorted order ever need to be considered - pairing two elements far apart in sorted order can only ever produce a LARGER difference for no sum benefit, so the DP only needs to decide, position by position, whether to pair the current element with its immediate sorted neighbor or leave it unpaired.

Recursively decide, for each element in the original array order, whether to leave it unpaired or pair it with some other still-unused element whose absolute difference with it is strictly less than k, trying all such combinatorial choices and taking the maximum sum achieved. This directly mirrors the problem statement (disjoint pairs, difference constraint, maximize sum) but explores an exponential number of pairing combinations since any two elements could potentially be paired. It is correct but completely impractical beyond tiny inputs. Time: O(2^n) Space: O(n)

Using the same sorted-adjacency insight as the better approach, replace the top-down recursion with an iterative bottom-up DP: dp[i] = max(dp[i-1], dp[i-2] + a[i] + a[i-1]) when a[i]-a[i-1] < k, filled left to right using only the previous two values. This avoids recursion call overhead and any risk of stack depth issues for larger n, and can be computed with just two rolling variables instead of a full array, achieving the same asymptotic time as the memoized version but with tighter constants. Time: O(n log n) Space: O(1) extra (beyond sorting)

First sort the array; this is the key insight, because if two elements are going to be validly paired (difference < k) and we want to maximize sum, it is never worse to pair adjacent elements in sorted order than to pair non-adjacent ones, so the search space collapses from all pairs to just adjacent-in-sorted-order-or-not. Then use a top-down recursive function with memoization over the sorted index i, where at each step you either skip element i or, if it can pair with i-1 (sorted difference < k), take both and add their sum, caching results by index to avoid recomputation. This reduces the exponential brute force down to a linear number of states, dominated by the initial sort. Time: O(n log n) Space: O(n)

1. Sort the array first - if any pair is worth taking, it's always at least as good to pair ADJACENT elements in sorted order (pairing across a gap only increases the difference without helping the sum). 2. dp[i] = best achievable sum using the first i elements of the sorted array; dp[i] = dp[i-1] (skip element i), OR dp[i-2]+arr[i-1]+arr[i] if those two adjacent sorted elements differ by less than k. 3. Take the better of the two options at every step; the final answer is dp[n].

Time: O(n log n), dominated by the initial sort - the DP pass afterward is O(n). Space: O(n) for the dp array (reducible to O(1) with just two running trackers).

Test a k small enough that no pair qualifies (answer 0), an odd n leaving one element unpaired, and n at the upper bound of 10^4.

Be ready to justify why only ADJACENT sorted pairs matter - a quick exchange-argument style explanation (any valid non-adjacent pairing could be rearranged to an adjacent one without hurting the sum or violating the difference constraint) demonstrates real understanding, not just pattern-matching the technique.