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
function maxSumSubarrayRemovingOneEle ( arr , n ) { let fw = [ ] ; let bw = [ ] ; let cur_max = arr [ 0 ] , max_so_far = arr [ 0 ] ; fw [ 0 ] = arr [ 0 ] ; for ( let i = 1 ; i < n ; i ++ ) { cur_max = Math . max ( arr [ i ] , cur_max + arr [ i ] ) ; max_so_far = Math . max ( max_so_far , cur_max ) ; fw [ i ] = cur_max ; } cur_max = max_so_far = bw [ n - 1 ] = arr [ n - 1 ] ; for ( let i = n - 2 ; i >= 0 ; i -- ) { cur_max = Math . max ( arr [ i ] , cur_max + arr [ i ] ) ; max_so_far = Math . max ( max_so_far , cur_max ) ; bw [ i ] = cur_max ; } let fans = max_so_far ; for ( let i = 1 ; i < n - 1 ; i ++ ) fans = Math . max ( fans , fw [ i - 1 ] + bw [ i + 1 ] ) ; return fans ; } let arr = [ - 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 ] ; let n = arr . length ; document . write ( maxSumSubarrayRemovingOneEle ( arr , n ) ) ;