Maximum subsequence sum such that no K elements are consecutive | Function to find the maximum sum of a subsequence consisting of no K consecutive array elements ; Stores states of dp ; Stores the prefix sum ; Update the prefix sum ; Base case for i < K ; For indices less than k take all the elements ; For i >= K case ; Skip each element from i to ( i - K + 1 ) to ensure that no K elements are consecutive ; Update the current dp state ; dp [ N ] stores the maximum sum ; Given array arr [ ] ; Function Call
function Max_Sum ( arr , K , N ) { var dp = Array ( N + 1 ) . fill ( 0 ) ; var prefix = Array ( N + 1 ) ; prefix [ 0 ] = 0 ; for ( var i = 1 ; i <= N ; i ++ ) { prefix [ i ] = prefix [ i - 1 ] + arr [ i - 1 ] ; } dp [ 0 ] = 0 ; for ( var i = 1 ; i < K ; i ++ ) { dp [ i ] = prefix [ i ] ; } for ( var i = K ; i <= N ; ++ i ) { for ( var j = i ; j >= ( i - K + 1 ) ; j -- ) { dp [ i ] = Math . max ( dp [ i ] , dp [ j - 1 ] + prefix [ i ] - prefix [ j ] ) ; } } return dp [ N ] ; } var arr = [ 4 , 12 , 22 , 18 , 34 , 12 , 25 ] ; var N = arr . length ; var K = 5 ; document . write ( Max_Sum ( arr , K , N ) ) ;