Maximum sum in an array such that every element has exactly one adjacent element to it | Java implementation of the approach ; To store the states of dp ; Function to return the maximized sum ; Base case ; Checks if a state is already solved ; Recurrence relation ; Return the result ; Driver code
import java . io . * ; class GFG { static int arrSize = 51 ; static int dp [ ] = new int [ arrSize ] ; static boolean v [ ] = new boolean [ arrSize ] ; static int sumMax ( int i , int arr [ ] , int n ) { if ( i >= n - 1 ) return 0 ; if ( v [ i ] ) return dp [ i ] ; v [ i ] = true ; dp [ i ] = Math . max ( arr [ i ] + arr [ i + 1 ] + sumMax ( i + 3 , arr , n ) , sumMax ( i + 1 , arr , n ) ) ; return dp [ i ] ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 1 , 1 , 1 } ; int n = arr . length ; System . out . println ( sumMax ( 0 , arr , n ) ) ; } }