Maximum subarray sum possible after removing at most one subarray | Function to find maximum subarray sum possible after removing at most one subarray ; Calculate the preSum [ ] array ; Update the value of sum ; Update the value of maxSum ; Update the value of preSum [ i ] ; Calculate the postSum [ ] array ; Update the value of sum ; Update the value of maxSum ; Update the value of postSum [ i ] ; Stores the resultant maximum sum of subarray ; Update the value of ans ; Print resultant sum ; Driver code
def maximumSum ( arr , n ) : NEW_LINE INDENT preSum = [ 0 ] * n NEW_LINE sum = 0 NEW_LINE maxSum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum = max ( arr [ i ] , sum + arr [ i ] ) NEW_LINE maxSum = max ( maxSum , sum ) NEW_LINE preSum [ i ] = maxSum NEW_LINE DEDENT sum = 0 NEW_LINE maxSum = 0 NEW_LINE postSum = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT sum = max ( arr [ i ] , sum + arr [ i ] ) NEW_LINE maxSum = max ( maxSum , sum ) NEW_LINE postSum [ i ] = maxSum NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT ans = max ( ans , preSum [ i ] + postSum [ i + 1 ] ) NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT arr = [ 7 , 6 , - 1 , - 4 , - 5 , 7 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE maximumSum ( arr , N ) NEW_LINE