Maximum subsequence sum such that no K elements are consecutive | Java 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
import java . io . * ; import java . util . * ; class GFG { public static int Max_Sum ( int [ ] arr , int K , int N ) { int [ ] dp = new int [ N + 1 ] ; Arrays . fill ( dp , 0 ) ; int [ ] prefix = new int [ 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 - 1 ; i ++ ) { dp [ i ] = prefix [ i ] ; } for ( int i = K ; i <= N ; ++ i ) { for ( int j = i ; j >= ( i - K + 1 ) ; j -- ) { dp [ i ] = Math . max ( dp [ i ] , dp [ j - 1 ] + prefix [ i ] - prefix [ j ] ) ; } } return dp [ N ] ; } public static void main ( String [ ] args ) { int [ ] arr = { 4 , 12 , 22 , 18 , 34 , 12 , 25 } ; int N = arr . length ; int K = 5 ; System . out . println ( Max_Sum ( arr , K , N ) ) ; } }