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 to test above methods
def maxSumSubarrayRemovingOneEle ( arr , n ) : NEW_LINE INDENT fw = [ 0 for k in range ( n ) ] NEW_LINE bw = [ 0 for k in range ( n ) ] NEW_LINE cur_max , max_so_far = arr [ 0 ] , arr [ 0 ] NEW_LINE fw [ 0 ] = cur_max NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT cur_max = max ( arr [ i ] , cur_max + arr [ i ] ) NEW_LINE max_so_far = max ( max_so_far , cur_max ) NEW_LINE fw [ i ] = cur_max NEW_LINE DEDENT cur_max = max_so_far = bw [ n - 1 ] = arr [ n - 1 ] NEW_LINE i = n - 2 NEW_LINE while i >= 0 : NEW_LINE INDENT cur_max = max ( arr [ i ] , cur_max + arr [ i ] ) NEW_LINE max_so_far = max ( max_so_far , cur_max ) NEW_LINE bw [ i ] = cur_max NEW_LINE i -= 1 NEW_LINE DEDENT fans = max_so_far NEW_LINE for i in range ( 1 , n - 1 ) : NEW_LINE INDENT fans = max ( fans , fw [ i - 1 ] + bw [ i + 1 ] ) NEW_LINE DEDENT return fans NEW_LINE DEDENT arr = [ - 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 ] NEW_LINE n = len ( arr ) NEW_LINE print maxSumSubarrayRemovingOneEle ( arr , n ) NEW_LINE