Maximum sum alternating subsequence | Return sum of maximum sum alternating sequence starting with arr [ 0 ] and is first decreasing . ; handling the edge case ; stores sum of decreasing and increasing sub - sequence ; store sum of increasing and decreasing sun - sequence ; As per question , first element must be part of solution . ; Traverse remaining elements of array ; IF current sub - sequence is decreasing the update dec [ j ] if needed . dec [ i ] by current inc [ j ] + arr [ i ] ; Revert the flag , if first decreasing is found ; If next element is greater but flag should be 1 i . e . this element should be counted after the first decreasing element gets counted ; If current sub - sequence is increasing then update inc [ i ] ; find maximum sum in b / w inc [ ] and dec [ ] ; return maximum sum alternate sun - sequence ; Driver Code
< ? php function maxAlternateSum ( $ arr , $ n ) { if ( $ n == 1 ) return $ arr [ 0 ] ; $ min = $ arr [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { $ min = max ( $ min , $ arr [ $ i ] ) ; } if ( $ arr [ 0 ] == $ min ) return $ arr [ 0 ] ; $ dec = array_fill ( 0 , $ n , 0 ) ; $ inc = array_fill ( 0 , $ n , 0 ) ; $ dec [ 0 ] = $ inc [ 0 ] = $ arr [ 0 ] ; $ flag = 0 ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { for ( $ j = 0 ; $ j < $ i ; $ j ++ ) { if ( $ arr [ $ j ] > $ arr [ $ i ] ) { $ dec [ $ i ] = max ( $ dec [ $ i ] , $ inc [ $ j ] + $ arr [ $ i ] ) ; $ flag = 1 ; } else if ( $ arr [ $ j ] < $ arr [ $ i ] && $ flag == 1 ) $ inc [ $ i ] = max ( $ inc [ $ i ] , $ dec [ $ j ] + $ arr [ $ i ] ) ; } } $ result = - ( PHP_INT_MAX - 1 ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { if ( $ result < $ inc [ $ i ] ) $ result = $ inc [ $ i ] ; if ( $ result < $ dec [ $ i ] ) $ result = $ dec [ $ i ] ; } return $ result ; } $ arr = array ( 8 , 2 , 3 , 5 , 7 , 9 , 10 ) ; $ n = sizeof ( $ arr ) ; echo " Maximum ▁ sum ▁ = ▁ " , maxAlternateSum ( $ arr , $ n ) ; ? >