Maximum subsequence sum such that no K elements are consecutive | C ++ program for the above approach ; Function to find the maximum sum of a subsequence consisting of no K consecutive array elements ; Stores states of dp ; Initialise dp state ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int Max_Sum ( int arr [ ] , int K , int N ) { int dp [ N + 1 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; int prefix [ N + 1 ] ; prefix [ 0 ] = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { prefix [ i ] = prefix [ i - 1 ] + arr [ i - 1 ] ; } dp [ 0 ] = 0 ; for ( int i = 1 ; i < K ; i ++ ) { dp [ i ] = prefix [ i ] ; } for ( int i = K ; i <= N ; ++ i ) { for ( int j = i ; j >= ( i - K + 1 ) ; j -- ) { dp [ i ] = max ( dp [ i ] , dp [ j - 1 ] + prefix [ i ] - prefix [ j ] ) ; } } return dp [ N ] ; } int main ( ) { int arr [ ] = { 4 , 12 , 22 , 18 , 34 , 12 , 25 } ; int N = sizeof ( arr ) / sizeof ( int ) ; int K = 5 ; cout << Max_Sum ( arr , K , N ) ; return 0 ; }