Maximum sum of pairs with specific difference | method to return maximum sum we can 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
< ? php function maxSumPairWithDifferenceLessThanK ( $ arr , $ N , $ K ) { sort ( $ arr ) ; $ dp = array ( ) ; $ dp [ 0 ] = 0 ; for ( $ i = 1 ; $ i < $ N ; $ i ++ ) { $ dp [ $ i ] = $ dp [ $ i - 1 ] ; if ( $ arr [ $ i ] - $ arr [ $ i - 1 ] < $ K ) { if ( $ i >= 2 ) $ dp [ $ i ] = max ( $ dp [ $ i ] , $ dp [ $ i - 2 ] + $ arr [ $ i ] + $ arr [ $ i - 1 ] ) ; else $ dp [ $ i ] = max ( $ dp [ $ i ] , $ arr [ $ i ] + $ arr [ $ i - 1 ] ) ; } } return $ dp [ $ N - 1 ] ; } $ arr = array ( 3 , 5 , 10 , 15 , 17 , 12 , 9 ) ; $ N = sizeof ( $ arr ) ; $ K = 4 ; echo maxSumPairWithDifferenceLessThanK ( $ arr , $ N , $ K ) ; ? >