Maximum sum of non | Java program to implement above approach ; Variable to store states of dp ; Variable to check if a given state has been solved ; Function to find the maximum sum subsequence such that no two elements are adjacent ; Base case ; To check if a state has been solved ; Variable to store prefix sum for sub - array { i , j } ; Required recurrence relation ; Returning the value ; Driver code ; Input array
import java . io . * ; class GFG { static int maxLen = 10 ; static int dp [ ] = new int [ maxLen ] ; static boolean [ ] visit = new boolean [ maxLen ] ; static int maxSum ( int arr [ ] , int i , int n , int k ) { if ( i >= n ) return 0 ; if ( visit [ i ] ) return dp [ i ] ; visit [ i ] = true ; int tot = 0 ; dp [ i ] = maxSum ( arr , i + 1 , n , k ) ; for ( int j = i ; j < ( i + k ) && ( j < n ) ; j ++ ) { tot += arr [ j ] ; dp [ i ] = Math . max ( dp [ i ] , tot + maxSum ( arr , j + 2 , n , k ) ) ; } return dp [ i ] ; } public static void main ( String [ ] args ) { int arr [ ] = { - 1 , 2 , - 3 , 4 , 5 } ; int k = 2 ; int n = arr . length ; System . out . println ( maxSum ( arr , 0 , n , k ) ) ; } }