Maximum sum in circular array such that no two elements are adjacent | Function to calculate the sum from 0 th position to ( n - 2 ) th position ; copy the element of original array to dp [ ] ; find the maximum element in the array ; start from 2 nd to n - 1 th pos ; traverse for all pairs bottom - up approach ; dp - condition ; find maximum sum ; return the maximum ; Function to find the maximum sum from 1 st position to n - 1 - th position ; Traverse from third to n - th pos ; bootom - up approach ; dp condition ; find max sum ; return max ; Driver Code
< ? php function maxSum1 ( $ arr , $ n ) { $ dp [ $ n ] = array ( ) ; $ maxi = 0 ; for ( $ i = 0 ; $ i < $ n - 1 ; $ i ++ ) { $ dp [ $ i ] = $ arr [ $ i ] ; if ( $ maxi < $ arr [ $ i ] ) $ maxi = $ arr [ $ i ] ; } for ( $ i = 2 ; $ i < $ n - 1 ; $ i ++ ) { for ( $ j = 0 ; $ j < $ i - 1 ; $ j ++ ) { if ( $ dp [ $ i ] < $ dp [ $ j ] + $ arr [ $ i ] ) { $ dp [ $ i ] = $ dp [ $ j ] + $ arr [ $ i ] ; if ( $ maxi < $ dp [ $ i ] ) $ maxi = $ dp [ $ i ] ; } } } return $ maxi ; } function maxSum2 ( $ arr , $ n ) { $ dp [ $ n ] = array ( ) ; $ maxi = 0 ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { $ dp [ $ i ] = $ arr [ $ i ] ; if ( $ maxi < $ arr [ $ i ] ) $ maxi = $ arr [ $ i ] ; } for ( $ i = 3 ; $ i < $ n ; $ i ++ ) { for ( $ j = 1 ; $ j < $ i - 1 ; $ j ++ ) { if ( $ dp [ $ i ] < $ arr [ $ i ] + $ dp [ $ j ] ) { $ dp [ $ i ] = $ arr [ $ i ] + $ dp [ $ j ] ; if ( $ maxi < $ dp [ $ i ] ) $ maxi = $ dp [ $ i ] ; } } } return $ maxi ; } function findMaxSum ( $ arr , $ n ) { return max ( maxSum1 ( $ arr , $ n ) , maxSum2 ( $ arr , $ n ) ) ; } $ arr = array ( 1 , 2 , 3 , 1 ) ; $ n = sizeof ( $ arr ) ; echo findMaxSum ( $ arr , $ n ) ; ? >