Maximum subsequence sum such that no three are consecutive | PHP program to find the maximum sum such that no three are consecutive using recursion . ; Returns maximum subsequence sum such that no three elements are consecutive ; Base cases ( process first three elements ) ; Process rest of the elements We have three cases ; Driver code
< ? php $ arr = array ( 100 , 1000 , 100 , 1000 , 1 ) ; $ sum = array_fill ( 0 , count ( $ arr ) + 1 , -1 ) ; function maxSumWO3Consec ( $ n ) { global $ sum , $ arr ; if ( $ sum [ $ n ] != -1 ) return $ sum [ $ n ] ; if ( $ n == 0 ) return $ sum [ $ n ] = 0 ; if ( $ n == 1 ) return $ sum [ $ n ] = $ arr [ 0 ] ; if ( $ n == 2 ) return $ sum [ $ n ] = $ arr [ 1 ] + $ arr [ 0 ] ; return $ sum [ $ n ] = max ( max ( maxSumWO3Consec ( $ n - 1 ) , maxSumWO3Consec ( $ n - 2 ) + $ arr [ $ n ] ) , $ arr [ $ n ] + $ arr [ $ n - 1 ] + maxSumWO3Consec ( $ n - 3 ) ) ; } $ n = count ( $ arr ) ; echo maxSumWO3Consec ( $ n ) ; ? >