Maximize sum of an Array by flipping sign of all elements of a single subarray | Python3 program for the above approach ; Function to find the maximum sum after flipping a subarray ; Stores the total sum of array ; Initialize the maximum sum ; Iterate over all possible subarrays ; Initialize sum of the subarray before flipping sign ; Initialize sum of subarray after flipping sign ; Calculate the sum of original subarray ; Subtract the original subarray sum and add the flipped subarray sum to the total sum ; Return the max_sum ; Driver Code ; Function call
import sys NEW_LINE def maxSumFlip ( a , n ) : NEW_LINE INDENT total_sum = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT total_sum += a [ i ] NEW_LINE DEDENT max_sum = - sys . maxsize - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sum = 0 NEW_LINE flip_sum = 0 NEW_LINE for j in range ( i , n ) : NEW_LINE INDENT sum += a [ j ] NEW_LINE max_sum = max ( max_sum , total_sum - 2 * sum ) NEW_LINE DEDENT DEDENT return max ( max_sum , total_sum ) NEW_LINE DEDENT arr = [ - 2 , 3 , - 1 , - 4 , - 2 ] NEW_LINE N = len ( arr ) NEW_LINE print ( maxSumFlip ( arr , N ) ) NEW_LINE