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 ; Driver Code ; Given array arr [ ] ; Function call
def Max_Sum ( arr , K , N ) : NEW_LINE INDENT dp = [ 0 ] * ( N + 1 ) NEW_LINE prefix = [ None ] * ( N + 1 ) NEW_LINE prefix [ 0 ] = 0 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT prefix [ i ] = prefix [ i - 1 ] + arr [ i - 1 ] NEW_LINE DEDENT dp [ 0 ] = 0 NEW_LINE for i in range ( 1 , K ) : NEW_LINE INDENT dp [ i ] = prefix [ i ] NEW_LINE DEDENT for i in range ( K , N + 1 ) : NEW_LINE INDENT for j in range ( i , i - K , - 1 ) : NEW_LINE INDENT dp [ i ] = max ( dp [ i ] , dp [ j - 1 ] + prefix [ i ] - prefix [ j ] ) NEW_LINE DEDENT DEDENT return dp [ N ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 4 , 12 , 22 , 18 , 34 , 12 , 25 ] NEW_LINE N = len ( arr ) NEW_LINE K = 5 NEW_LINE print ( Max_Sum ( arr , K , N ) ) NEW_LINE DEDENT