Maximize the maximum subarray sum after removing atmost one element | Function to return the maximum sub - array sum ; Initialized ; Traverse in the array ; Increase the sum ; If sub - array sum is more than the previous ; If sum is negative ; Function that returns the maximum sub - array sum after removing an element from the same sub - array ; Maximum sub - array sum using Kadane 's Algorithm ; Re - apply Kadane 's with minor changes ; Increase the sum ; If sub - array sum is greater than the previous ; If elements are 0 , no removal ; If elements are more , then store the minimum value in the sub - array obtained till now ; If sum is negative ; Re - initialize everything ; Driver code
< ? php function maxSubArraySum ( $ a , $ size ) { $ max_so_far = PHP_INT_MIN ; $ max_ending_here = 0 ; for ( $ i = 0 ; $ i < $ size ; $ i ++ ) { $ max_ending_here = $ max_ending_here + $ a [ $ i ] ; if ( $ max_so_far < $ max_ending_here ) $ max_so_far = $ max_ending_here ; if ( $ max_ending_here < 0 ) $ max_ending_here = 0 ; } return $ max_so_far ; } function maximizeSum ( $ a , $ n ) { $ cnt = 0 ; $ mini = PHP_INT_MAX ; $ minSubarray = PHP_INT_MAX ; $ sum = maxSubArraySum ( $ a , $ n ) ; $ max_so_far = PHP_INT_MIN ; $ max_ending_here = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { $ max_ending_here = $ max_ending_here + $ a [ $ i ] ; $ cnt ++ ; $ minSubarray = min ( $ a [ $ i ] , $ minSubarray ) ; if ( $ sum == $ max_ending_here ) { if ( $ cnt == 1 ) $ mini = min ( $ mini , 0 ) ; else $ mini = min ( $ mini , $ minSubarray ) ; } if ( $ max_ending_here < 0 ) { $ max_ending_here = 0 ; $ cnt = 0 ; $ minSubarray = PHP_INT_MAX ; } } return $ sum - $ mini ; } $ a = array ( 1 , 2 , 3 , -2 , 3 ) ; $ n = sizeof ( $ a ) / sizeof ( $ a [ 0 ] ) ; echo maximizeSum ( $ a , $ n ) ; ? >