Maximum sum subarray removing at most one element | Method returns maximum sum of all subarray where removing one element is also allowed ; Maximum sum subarrays in forward and backward directions ; Initialize current max and max so far . ; calculating maximum sum subarrays in forward direction ; storing current maximum till ith , in forward array ; calculating maximum sum subarrays in backward direction ; storing current maximum from ith , in backward array ; Initializing final ans by max_so_far so that , case when no element is removed to get max sum subarray is also handled ; choosing maximum ignoring ith element ; Driver Code
< ? php function maxSumSubarrayRemovingOneEle ( $ arr , $ n ) { $ fw = array ( ) ; $ bw = array ( ) ; $ cur_max = $ arr [ 0 ] ; $ max_so_far = $ arr [ 0 ] ; $ fw [ 0 ] = $ arr [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { $ cur_max = max ( $ arr [ $ i ] , $ cur_max + $ arr [ $ i ] ) ; $ max_so_far = max ( $ max_so_far , $ cur_max ) ; $ fw [ $ i ] = $ cur_max ; } $ cur_max = $ max_so_far = $ bw [ $ n - 1 ] = $ arr [ $ n - 1 ] ; for ( $ i = $ n - 2 ; $ i >= 0 ; $ i -- ) { $ cur_max = max ( $ arr [ $ i ] , $ cur_max + $ arr [ $ i ] ) ; $ max_so_far = max ( $ max_so_far , $ cur_max ) ; $ bw [ $ i ] = $ cur_max ; } $ fans = $ max_so_far ; for ( $ i = 1 ; $ i < $ n - 1 ; $ i ++ ) $ fans = max ( $ fans , $ fw [ $ i - 1 ] + $ bw [ $ i + 1 ] ) ; return $ fans ; } $ arr = array ( -2 , -3 , 4 , -1 , -2 , 1 , 5 , -3 ) ; $ n = count ( $ arr ) ; echo maxSumSubarrayRemovingOneEle ( $ arr , $ n ) ; ? >