Maximum sum of pairwise product in an array with negative allowed | Python3 code for above implementation ; Function to find the maximum sum ; Sort the array first ; First multiply negative numbers pairwise and sum up from starting as to get maximum sum . ; Second multiply positive numbers pairwise and summed up from the last as to get maximum sum . ; To handle case if positive and negative numbers both are odd in counts . ; If one of them occurs odd times ; Driver code
Mod = 1000000007 NEW_LINE def findSum ( arr , n ) : NEW_LINE INDENT sum = 0 NEW_LINE arr . sort ( ) NEW_LINE i = 0 NEW_LINE while i < n and arr [ i ] < 0 : NEW_LINE INDENT if i != n - 1 and arr [ i + 1 ] <= 0 : NEW_LINE INDENT sum = ( sum + ( arr [ i ] * arr [ i + 1 ] ) % Mod ) % Mod NEW_LINE i += 2 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT j = n - 1 NEW_LINE while j >= 0 and arr [ j ] > 0 : NEW_LINE INDENT if j != 0 and arr [ j - 1 ] > 0 : NEW_LINE INDENT sum = ( sum + ( arr [ j ] * arr [ j - 1 ] ) % Mod ) % Mod NEW_LINE j -= 2 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if j > i : NEW_LINE INDENT sum = ( sum + ( arr [ i ] * arr [ j ] ) % Mod ) % Mod NEW_LINE DEDENT elif i == j : NEW_LINE INDENT sum = ( sum + arr [ i ] ) % Mod NEW_LINE DEDENT return sum NEW_LINE DEDENT arr = [ - 1 , 9 , 4 , 5 , - 4 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE print ( findSum ( arr , n ) ) NEW_LINE