Maximize Array sum after changing sign of any elements for exactly M times | Function to find the maximum sum with M flips ; Declare a priority queue i . e . min heap ; Declare the sum as zero ; Push all elements of the array in it ; Iterate for M times ; Get the top element ; Flip the sign of the top element ; Remove the top element ; Update the sum ; Push the temp into the queue ; Driver program ; Given input
def findMaximumSumWithMflips ( arr , N , M ) : NEW_LINE INDENT pq = [ ] NEW_LINE sum = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT pq . append ( arr [ i ] ) NEW_LINE sum += arr [ i ] NEW_LINE pq . sort ( ) NEW_LINE DEDENT while ( M > 0 ) : NEW_LINE INDENT sum -= pq [ 0 ] NEW_LINE temp = - 1 * pq [ 0 ] NEW_LINE pq = pq [ 1 : ] NEW_LINE sum += temp NEW_LINE pq . append ( temp ) NEW_LINE pq . sort ( ) NEW_LINE M -= 1 NEW_LINE DEDENT print ( sum ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ - 3 , 7 , - 1 , - 5 , - 3 ] NEW_LINE N = len ( arr ) NEW_LINE M = 4 NEW_LINE findMaximumSumWithMflips ( arr , N , M ) NEW_LINE DEDENT