Maximum sum such that no two elements are adjacent | Set 2 | PHP 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 ; Required recurrence relation ; Returning the value ; Driver code
< ? php $ maxLen = 10 ; $ dp = array_fill ( 0 , $ GLOBALS [ ' axLen ' , 0 ) ; $ v = array_fill ( 0 , $ GLOBALS [ ' axLen ' , 0 ) ; function maxSum ( $ arr , $ i , $ n ) { if ( $ i >= $ n ) return 0 ; if ( $ GLOBALS [ ' v ' ] [ $ i ] ) return $ GLOBALS [ ' dp ' ] [ $ i ] ; $ GLOBALS [ ' v ' ] [ $ i ] = 1 ; $ GLOBALS [ ' dp ' ] [ $ i ] = max ( maxSum ( $ arr , $ i + 1 , $ n ) , $ arr [ $ i ] + maxSum ( $ arr , $ i + 2 , $ n ) ) ; return $ GLOBALS [ ' dp ' ] [ $ i ] ; } $ arr = array ( 12 , 9 , 7 , 33 ) ; $ n = count ( $ arr ) ; echo maxSum ( $ arr , 0 , $ n ) ; ? >