Maximize the sum of array after multiplying a prefix and suffix by | Kadane 's algorithm to find the maximum subarray sum ; Loop to find the maximum subarray array sum in the given array ; Function to find the maximum sum of the array by multiplying the prefix and suffix by - 1 ; Total intital sum ; Loop to find the maximum sum of the array ; Maximum value ; Driver Code
def maxSubArraySum ( a , size ) : NEW_LINE INDENT max_so_far = - 10 ** 9 NEW_LINE max_ending_here = 0 NEW_LINE for i in range ( size ) : NEW_LINE INDENT max_ending_here = max_ending_here + a [ i ] NEW_LINE if ( max_ending_here < 0 ) : NEW_LINE INDENT max_ending_here = 0 NEW_LINE DEDENT if ( max_so_far < max_ending_here ) : NEW_LINE INDENT max_so_far = max_ending_here NEW_LINE DEDENT DEDENT return max_so_far NEW_LINE DEDENT def maxSum ( a , n ) : NEW_LINE INDENT S = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT S += a [ i ] NEW_LINE DEDENT X = maxSubArraySum ( a , n ) NEW_LINE return 2 * X - S NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ - 1 , - 2 , - 3 ] NEW_LINE n = len ( a ) NEW_LINE max_sum = maxSum ( a , n ) NEW_LINE print ( max_sum ) NEW_LINE DEDENT