Maximise array sum after taking non | Java implementation of the approach ; To store the states of dp ; To check if a given state has been solved ; To store the prefix - sum ; Function to fill the prefix_sum [ ] with the prefix sum of the given array ; Function to find the maximum sum subsequence such that no two elements are adjacent ; Base case ; To check if a state has been solved ; Required recurrence relation ; Returning the value ; Driver code ; Finding prefix - sum ; Finding the maximum possible sum
import java . util . * ; class GFG { static int maxLen = 10 ; static int [ ] dp = new int [ maxLen ] ; static boolean [ ] v = new boolean [ maxLen ] ; static int [ ] prefix_sum = new int [ maxLen ] ; static void findPrefixSum ( int arr [ ] , int n ) { prefix_sum [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) { prefix_sum [ i ] = arr [ i ] + prefix_sum [ i - 1 ] ; } } static int maxSum ( int arr [ ] , int i , int n , int k ) { if ( i + k > n ) { return 0 ; } if ( v [ i ] ) { return dp [ i ] ; } v [ i ] = true ; int x ; if ( i == 0 ) { x = prefix_sum [ k - 1 ] ; } else { x = prefix_sum [ i + k - 1 ] - prefix_sum [ i - 1 ] ; } dp [ i ] = Math . max ( maxSum ( arr , i + 1 , n , k ) , x + maxSum ( arr , i + k + 1 , n , k ) ) ; return dp [ i ] ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 3 , 7 , 6 } ; int n = arr . length ; int k = 1 ; findPrefixSum ( arr , n ) ; System . out . println ( maxSum ( arr , 0 , n , k ) ) ; } }