Maximum sum possible for a sub | Java implementation of the approach ; Function to return the maximum sum possible ; dp [ i ] represent the maximum sum so far after reaching current position i ; Initialize dp [ 0 ] ; Initialize the dp values till k since any two elements included in the sub - sequence must be atleast k indices apart , and thus first element and second element will be k indices apart ; Fill remaining positions ; Return the maximum sum ; Driver code
class GFG { static int maxSum ( int [ ] arr , int k , int n ) { if ( n == 0 ) return 0 ; if ( n == 1 ) return arr [ 0 ] ; if ( n == 2 ) return Math . max ( arr [ 0 ] , arr [ 1 ] ) ; int [ ] dp = new int [ n ] ; dp [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i <= k ; i ++ ) dp [ i ] = Math . max ( arr [ i ] , dp [ i - 1 ] ) ; for ( int i = k + 1 ; i < n ; i ++ ) dp [ i ] = Math . max ( arr [ i ] , dp [ i - ( k + 1 ) ] + arr [ i ] ) ; return maximum ( dp ) ; } static int maximum ( int [ ] arr ) { int max = Integer . MIN_VALUE ; for ( int i = 0 ; i < arr . length ; i ++ ) { if ( arr [ i ] > max ) { max = arr [ i ] ; } } return max ; } public static void main ( String [ ] args ) { int [ ] arr = { 6 , 7 , 1 , 3 , 8 , 2 , 4 } ; int n = arr . length ; int k = 2 ; System . out . println ( maxSum ( arr , k , n ) ) ; } }