Maximum sum possible for a sub | 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
function maxSum ( arr , k , n ) { if ( n == 0 ) return 0 ; if ( n == 1 ) return arr [ 0 ] ; if ( n == 2 ) return Math . max ( arr [ 0 ] , arr [ 1 ] ) ; let dp = new Array ( n ) ; dp [ 0 ] = arr [ 0 ] ; for ( let i = 1 ; i <= k ; i ++ ) dp [ i ] = Math . max ( arr [ i ] , dp [ i - 1 ] ) ; for ( let i = k + 1 ; i < n ; i ++ ) dp [ i ] = Math . max ( arr [ i ] , dp [ i - ( k + 1 ) ] + arr [ i ] ) ; let max = Number . MIN_VALUE ; for ( let i = 0 ; i < dp . length ; i ++ ) { max = Math . max ( max , dp [ i ] ) ; } return max ; } let arr = [ 6 , 7 , 1 , 3 , 8 , 2 , 4 ] ; let n = arr . length ; let k = 2 ; document . write ( maxSum ( arr , k , n ) ) ;