Maximum sum of pairs with specific difference | Java program to find maximum pair sum whose difference is less than K ; 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 to test above methods
import java . io . * ; import java . util . * ; class GFG { static int maxSumPairWithDifferenceLessThanK ( int arr [ ] , int N , int K ) { Arrays . sort ( arr ) ; int dp [ ] = new int [ N ] ; dp [ 0 ] = 0 ; for ( int i = 1 ; i < N ; i ++ ) { dp [ i ] = dp [ i - 1 ] ; if ( arr [ i ] - arr [ i - 1 ] < K ) { if ( i >= 2 ) dp [ i ] = Math . max ( dp [ i ] , dp [ i - 2 ] + arr [ i ] + arr [ i - 1 ] ) ; else dp [ i ] = Math . max ( dp [ i ] , arr [ i ] + arr [ i - 1 ] ) ; } } return dp [ N - 1 ] ; } public static void main ( String [ ] args ) { int arr [ ] = { 3 , 5 , 10 , 15 , 17 , 12 , 9 } ; int N = arr . length ; int K = 4 ; System . out . println ( maxSumPairWithDifferenceLessThanK ( arr , N , K ) ) ; } }