Maximum sum of pairs with specific difference | method to return maximum sum we can get by get by finding less than K difference pair ; Sort input array in ascending order . ; dp [ i ] denotes the maximum disjoint pair sum we can achieve using first i elements ; if no element then dp value will be 0 ; first give previous value to dp [ i ] i . e . no pairing with ( i - 1 ) th element ; if current and previous element can form a pair ; update dp [ i ] by choosing maximum between pairing and not pairing ; last index will have the result ; Driver code to test above methods
def maxSumPairWithDifferenceLessThanK ( arr , N , K ) : NEW_LINE INDENT arr . sort ( ) NEW_LINE dp = [ 0 ] * N NEW_LINE dp [ 0 ] = 0 NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT dp [ i ] = dp [ i - 1 ] NEW_LINE if ( arr [ i ] - arr [ i - 1 ] < K ) : NEW_LINE INDENT if ( i >= 2 ) : NEW_LINE INDENT dp [ i ] = max ( dp [ i ] , dp [ i - 2 ] + arr [ i ] + arr [ i - 1 ] ) ; NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] = max ( dp [ i ] , arr [ i ] + arr [ i - 1 ] ) ; NEW_LINE DEDENT DEDENT DEDENT return dp [ N - 1 ] NEW_LINE DEDENT arr = [ 3 , 5 , 10 , 15 , 17 , 12 , 9 ] NEW_LINE N = len ( arr ) NEW_LINE K = 4 NEW_LINE print ( maxSumPairWithDifferenceLessThanK ( arr , N , K ) ) NEW_LINE