Maximum sum subsequence with values differing by at least 2 | Java program to find maximum sum subsequence with values differing by at least 2 ; Function to find maximum sum subsequence such that two adjacent values elements are not selected ; map to store the frequency of array elements ; Make a dp array to store answer upto i th value ; Base cases ; Iterate for all possible values of arr [ i ] ; Return the last value ; Driver code
import java . util . * ; import java . lang . * ; class GFG { public static int get_max_sum ( int arr [ ] , int n ) { HashMap < Integer , Integer > freq = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( freq . containsKey ( arr [ i ] ) ) { int x = freq . get ( arr [ i ] ) ; freq . replace ( arr [ i ] , x + 1 ) ; } else freq . put ( arr [ i ] , 1 ) ; } int [ ] dp = new int [ 100001 ] ; for ( int i = 0 ; i < 100001 ; i ++ ) dp [ i ] = 0 ; dp [ 0 ] = 0 ; if ( freq . containsKey ( 0 ) ) dp [ 1 ] = freq . get ( 0 ) ; else dp [ 1 ] = 0 ; for ( int i = 2 ; i <= 100000 ; i ++ ) { int temp = ( freq . containsKey ( i ) ) ? freq . get ( i ) : 0 ; dp [ i ] = Math . max ( dp [ i - 1 ] , dp [ i - 2 ] + i * temp ) ; } return dp [ 100000 ] ; } public static void main ( String [ ] args ) { int N = 3 ; int arr [ ] = { 2 , 2 , 3 } ; System . out . println ( get_max_sum ( arr , N ) ) ; } }