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
function maxSubArraySum ( a , size ) { let max_so_far = Number . MIN_VALUE , max_ending_here = 0 ; for ( let 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 ) { let cnt = 0 ; let mini = Number . MAX_VALUE ; let minSubarray = Number . MAX_VALUE ; let sum = maxSubArraySum ( a , n ) ; let max_so_far = Number . MIN_VALUE , max_ending_here = 0 ; for ( let i = 0 ; i < n ; i ++ ) { max_ending_here = max_ending_here + a [ i ] ; cnt ++ ; minSubarray = Math . min ( a [ i ] , minSubarray ) ; if ( sum == max_ending_here ) { if ( cnt == 1 ) mini = Math . min ( mini , 0 ) ; else mini = Math . min ( mini , minSubarray ) ; } if ( max_ending_here < 0 ) { max_ending_here = 0 ; cnt = 0 ; minSubarray = Integer . MAX_VALUE ; } } return sum - mini ; } let a = [ 1 , 2 , 3 , - 2 , 3 ] ; let n = a . length ; document . write ( maximizeSum ( a , n ) ) ;