Maximum sum bitonic subarray | function to find the maximum sum bitonic subarray ; ' msis [ ] ' to store the maximum sum increasing subarray up to each index of ' arr ' from the beginning ' msds [ ] ' to store the maximum sum decreasing subarray from each index of ' arr ' up to the end ; to store the maximum sum bitonic subarray ; building up the maximum sum increasing subarray for each array index ; building up the maximum sum decreasing subarray for each array index ; for each array index , calculating the maximum sum of bitonic subarray of which it is a part of ; if true , then update ' max ' bitonic subarray sum ; required maximum sum ; Driver Code
< ? php function maxSumBitonicSubArr ( $ arr , $ n ) { $ msis = array ( ) ; $ msds = array ( ) ; $ max_sum = PHP_INT_MIN ; $ msis [ 0 ] = $ arr [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) if ( $ arr [ $ i ] > $ arr [ $ i - 1 ] ) $ msis [ $ i ] = $ msis [ $ i - 1 ] + $ arr [ $ i ] ; else $ msis [ $ i ] = $ arr [ $ i ] ; $ msds [ $ n - 1 ] = $ arr [ $ n - 1 ] ; for ( $ i = $ n - 2 ; $ i >= 0 ; $ i -- ) if ( $ arr [ $ i ] > $ arr [ $ i + 1 ] ) $ msds [ $ i ] = $ msds [ $ i + 1 ] + $ arr [ $ i ] ; else $ msds [ $ i ] = $ arr [ $ i ] ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) if ( $ max_sum < ( $ msis [ $ i ] + $ msds [ $ i ] - $ arr [ $ i ] ) ) $ max_sum = $ msis [ $ i ] + $ msds [ $ i ] - $ arr [ $ i ] ; return $ max_sum ; } $ arr = array ( 5 , 3 , 9 , 2 , 7 , 6 , 4 ) ; $ n = sizeof ( $ arr ) ; echo " Maximum ▁ Sum ▁ = ▁ " , maxSumBitonicSubArr ( $ arr , $ n ) ; ? >